[python3] 백준 14503번 - 로봇청소기

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은
N x N 크기의 직사각형으로 나타낼 수 있으며,
1 X 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표
(r,c) 로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가
(0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가
(N-1, M-1) 이다. 즉, 좌표
(r, c) 는 북쪽에서
(r+1) 번째에 있는 줄의 서쪽에서
(c+1) 번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
   2-1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2-2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
   3-1) 반시계 방향으로 90도회전한다.
   3-2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3-3) 1번으로 돌아간다.

입력

첫째 줄에 방의 크기 N과 M이 입력된다.
$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표
$(r, c)$와 처음에 로봇 청소기가 바라보는 방향
$d$가 입력된다.
$d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다.
$i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다.
방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

코드

def DFS(x,y,dir):
    global cnt
    check = 1
    if board[x][y] == 0:
        board[x][y] = 2
        cnt += 1
    for _ in range(4):
        dir = (dir+3) % 4
        newx = x + dx[dir]
        newy = y + dy[dir]
        if board[newx][newy] == 0:
            DFS(newx,newy,dir)
            check = 0
            return           
    if check:
        ndir = (dir+2) % 4
        if board[x+dx[ndir]][y+dy[ndir]] != 1:
            DFS(x+dx[ndir],y+dy[ndir],dir)
        else:
            return

if __name__ == "__main__":
    n,m = map(int,input().split())
    r,c,d = map(int,input().split())
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    board = []
    cnt = 0
    for _ in range(n):
        board.append(list(map(int,input().split())))
    DFS(r,c,d)
    print(cnt)

후기

문제에 가장 큰 point는 회전해서 이동하는 것이다.
1) 반시계로 회전하는 법
2) 후진하는 법

시계 방향으로 이동하는 것은 다음과 같다.

이 배열을 기준으로 반시계로 이동하려면
0번의 인덱스는 3으로, 3번의 인덱스는 2로 이동하면 된다.

따라서, 원래의 인덱스에서 3을 더해주고 4로 나눈 나머지값과 같다
dir = (dir + 3) % 4

후진의 방향은 다음과 같다.

원래의 방향은 유지한 채로 후진을 하는 것은 지금의 방향에서 반대방향이라는 뜻이다.
즉, 0은 2, 1은 3, 2는 0 이런식이다.
따라서, 원래의 인덱스에 2를 더하고 4로 나눈 나머지값과 같다
dir = (dir + 2) %4

그래서, 후진을 하고 싶을 때는 dir을 이렇게 반대로 만들어준다음 다시 반대로 만들어 원상복구 하면 된다.
원래 인덱스 -> 후진 인덱스 -> 원래 인덱스
이 과정을 거치는 것이다.

추가로,
코드에서는 0은 청소 가능한 방, 1은 벽이라고 했는데 추가로 청소가 완료된 방은 2라고 지정하여서 이미 청소가 한 방은 가지 않도록 하는 check의 역할을 하였다.