[백준] 14503: 로봇 청소기 python 구현 / DFS

문제

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

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

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

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 $90^\circ$ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

CODE

import sys
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
r, c, d = map(int, input().split())
Map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

direction = {0:[-1, 0], # 북(0)
             1:[0, 1],  # 동(90)
             2:[1, 0],  # 남(180)
             3:[0, -1]} # 서(270)
counterclock = [0, 3, 2, 1, 0, 3, 2, 1] # 반시계 방향으로

def backstep(di): # 후진
    return di+2 if di < 2 else di-2

# vst = [[0]*m for i in range(n)]
# 벽: 1, 청소x: 0, 청소o: 2
state = 1
clean_cnt = 0
def dfs(x, y, di):
    global clean_cnt, state
    if not state:
        return 
    
    # 현재 칸이 아직 청소되지 않은 경우 청소
    if not Map[x][y]:
        Map[x][y] = 2
        clean_cnt += 1
    
    cd = counterclock.index(di)
    for i in counterclock[cd+1:cd+5]:
        # 반시계 방향으로 회전하고
        nx = x + direction[i][0]
        ny = y + direction[i][1]
        
        if not state: continue
        if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
        if Map[nx][ny]: continue # 벽이거나 청소 한 경우 pass

        # 전진했을 때 청소되지 않은 빈칸이 있는 경우
        if not Map[nx][ny]: 
            Map[nx][ny] = 2 # 청소한다
            clean_cnt += 1
            dfs(nx, ny, i)
    
    # 다 검사했는데 4칸 중 청소되지 않은 빈 칸이 없는 경우
    # 움직일 수 있다면 방향을 유지한 채로 한칸 후진
    nx = x + direction[backstep(di)][0]
    ny = y + direction[backstep(di)][1]
    # 벽이라서 후진할 수 없으면 멈춤
    if Map[nx][ny]==1:
        state = 0
        return 
    else: # 후진할 수 있음 계속 청소
        dfs(nx, ny, di)

dfs(r, c, d)

print(clean_cnt)