[백준 14503] 로봇 청소기

1. 문제

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

2. 접근 방법

완전 시뮬 그 자체인 문제

 

근데 문제 이해하는게 너무 어려웠음

ㄹㅇ루 난독증인가 ㅠ

짜증 

 

여기서 말하는 그 방향이 뭔데요 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 어이업서(╬▔皿▔)╯

여튼 저 작동 로직에 대해 조금 더 풀어서 써보자면

 

1. 현재 위치를 청소한다.

2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다. 

------> 현재 방향을 기준으로 왼쪽 방향이므로 현재 '북쪽 방향'인경우 북쪽을 기준으로 왼쪽인 '왼쪽 방향' 부터 '남쪽 방향', '오른쪽 방향', '북쪽 방향' 이렇게 보면 된다.

-------> 현재 '왼쪽 방향'인 경우 왼쪽을 기준으로 왼쪽인 '남쪽 방향', '오른쪽 방향', '북쪽 방향', '왼쪽 방향' 순

-------> 현재 '남쪽 방향'인 경우 남쪽을 기준으로 왼쪽인 '오른쪽 방향', '북쪽 방향', '왼쪽 방향', '남쪽 방향' 순

-------> 현재 '오른쪽 방향'인 경우 오른쪽을 기준으로 왼쪽인 '북쪽 방향', '왼쪽 방향', '남쪽 방향', '오른쪽 방향' 순

2-a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

------> 여기서 왼쪽 방향이란 "현재 방향을 기준으로 한 왼쪽 방향"을 뜻하는 것

------> 따라서 "a o b" 에서 현재 위치가 o이고, 현재 방향이 남쪽이라면 남쪽을 기준으로 왼쪽 방향인 오른쪽 방향에 위치한 b의 청소 여부를 확인하면 된다. 이 때 b가 청소하지 않은 공간이라면  현재 방향을 오른쪽으로 바꾸고, 한칸 전진해서 현재 방향은 "오른쪽 방향" 이고, 현재 위치는 "b"가 된다.

2-b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

------> 여기서 말하는 "그 방향"이란 왼쪽 방향을 뜻한다. 즉 왼쪽 방향의 왼쪽 방향 .. 아니 그냥 반시계 방향이라고 하면 안되나요 ??????????????????????????????? 후 .. 여튼 예를 들어보자면, 현재 방향이 남쪽이라면 남쪽을 기준으로 왼쪽 방향인 오른쪽 방향에 위치한 요소의 청소 여부를 확인하고(2-a), 만약 해당 공간이 청소되어있다면 오른쪽 방향의 왼쪽 방향인 북쪽 방향에 위치한 요소의 청소 여부를 확인하라는 말 ..! 이렇게 해서 북쪽 방향도 청소가 되어있다면 이제 북쪽 방향의 왼쪽 방향인 왼쪽 방향에 위치한 요소의 청소 여부를 확인하면 된다.

2-c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

2-d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

이 로직을 잘 이해했다면 이제 구현만 하시면 됩니다 ^-^

 

사진으로 보면 요런 순서입니다 (테케 2번 기준)

 

구현 할 때 주의할 점이 몇가지가 있는데요 ^^

 

1. 

일단 방향을 뜻하는 숫자가 0이 "북", 1이 "동", 2가 "남", 3이 "서" 입니다.

하지만 현재 방향에서 왼쪽 방향으로, 즉 반시계 방향으로 방향을 회전하므로, 북 -> 서 -> 남 -> 동 이렇게 가야합니다.

3. 코드

python

def isBoard(x, y):
    if 0 <= x < M and 0 <= y < N:
        return True
    return False

def canClean(x, y):
    if isBoard(x, y):
        if visited[y][x] == 0 and board[y][x] != 1:
            return True
    return False

def rotateRobot(dir):
    return (dir+3)%4

def clean(x, y, d, cnt):
    global visited
    if visited[y][x] == 0:
        visited[y][x] = cnt

    for _ in range(4):
        nd = rotateRobot(d)
        nx = x + direction[nd][0]
        ny = y + direction[nd][1]
        if canClean(nx, ny):
            clean(nx, ny, nd, cnt+1)
            return
        else:
            d = nd
            continue

    nx = x - (direction[nd][0])
    ny = y - (direction[nd][1])
    no_cnt = 0
    for i in range(4):
        tx = nx + direction[nd][0]
        ty = ny + direction[nd][1]
        if visited[ty][tx] != 0 or board[ty][tx] == 1:
            no_cnt += 1

    if no_cnt == 4:
        if board[ny][nx] == 1:
            print(cnt)
            exit()
    if visited[ny][nx] == 0:
        clean(nx, ny, nd, cnt+1)
    else:
        clean(nx, ny, nd, cnt)



N, M = map(int, input().split())
sy, sx, sd = map(int, input().split())
# 북 동 남 서
direction = ((0, -1), (1, 0), (0, 1), (-1, 0))
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
answer = 0
clean(sx, sy, sd, 1)

4. 마치며

티스토리에다가 정리하다가

처음에는 return을 해서 풀었는데, 글을 쓰면서 다시 정리하다보니 (2-d)에서 return이 아니라 exit()를 해서 끝내버리면 더 빨라지겠다 싶은거예여 ???

왜냐면 return을 써버리면 재귀를 이용해서 깊이 들어간만큼 다시 빠져나와줘야하니까 cnt가 다시 1이 될 때까지 함수를 실행해줘야하자나여 ? 근데 어차피 저는 제일 깊게 들어갔을 때의 값이 필요한거니까 굳이 기다릴 필요가 없자나여 ???? 그래서 움직이지 못할 때(2-d)에서 cnt 프린트하고, exit()해서 끝내버리면 되겠다 싶어서 다시 제출했거든여 ??

 

꺄항

그랬더니 이게 반으로 줄어서 pypy가 아닌 python3으로 제출해도 시간도 줄고 메모리도 줄어들었습니다

짝짝짝

원래 코드

def isBoard(x, y):
    if 0 <= x < M and 0 <= y < N:
        return True
    return False

def canClean(x, y):
    if isBoard(x, y):
        if visited[y][x] == 0 and board[y][x] != 1:
            return True
    return False

def rotateRobot(dir):
    return (dir+3)%4

def clean(x, y, d, cnt):
    global visited
    if visited[y][x] == 0:
        visited[y][x] = cnt

    for _ in range(4):
        nd = rotateRobot(d)
        nx = x + direction[nd][0]
        ny = y + direction[nd][1]
        if canClean(nx, ny):
            clean(nx, ny, nd, cnt+1)
            return
        else:
            d = nd
            continue

    nx = x - (direction[nd][0])
    ny = y - (direction[nd][1])
    no_cnt = 0
    for i in range(4):
        tx = nx + direction[nd][0]
        ty = ny + direction[nd][1]
        if visited[ty][tx] != 0 or board[ty][tx] == 1:
            no_cnt += 1

    if no_cnt == 4:
        if board[ny][nx] == 1:
            return
    if visited[ny][nx] == 0:
        clean(nx, ny, nd, cnt+1)
    else:
        clean(nx, ny, nd, cnt)


N, M = map(int, input().split())
sy, sx, sd = map(int, input().split())
# 북 동 남 서
direction = ((0, -1), (1, 0), (0, 1), (-1, 0))
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
answer = 0
clean(sx, sy, sd, 1)
for i in range(len(visited)):
    answer = max(answer, max(visited[i]))
print(answer)