[백준 14503. 로봇 청소기]

문제

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

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

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

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

---

풀이

설명은 복잡해 보이지만 재귀를 활용한 간단한 시뮬레이션 문제였다.
테두리가 벽으로 주어지기 때문에 범위 밖을 나가는 경우를 생각하지 않아도 된다.

1. 처음위치에서 함수 시작 후 청소하지 않았으면 청소 표시
   (여기서 벽과 구분하기 위해 1이 아닌 다른 수로 지정해야한다.)
2. 사방탐색하면서 청소하지 않은 방 있다면 일단 방향전환
3. 앞의 칸이 청소 안한 방일때까지 회전
4. 찾으면 해당 위치로 재귀 호출
   (여기서 백트래킹이 아닌 바로 종료되는 조건이기 때문에 재귀 다음에 return 해줘야함)
5. for-else로 사방탐색이 다 끝난경우 후진 가능한지 판단
6. 후진 가능하면 후진 후 재귀, 아니면 종료

# memory: 31316KB , time: 44ms
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
r, c, dir = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 청소한 칸
cnt = 0
arr = [list(map(int, input().split())) for _ in range(N)]


def clean(r, c):
    global cnt
    global dir
    # 현재칸 청소 안했으면 청소
    if arr[r][c] == 0:
        arr[r][c] = 2
        cnt += 1
    # 사방 탐색 중 청소 안된 방 있으면
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if arr[nx][ny] == 0:
            # 일단 방향전환
            dir = (dir - 1) % 4
            # 앞의 칸이 청소 안한 칸일때까지 회전
            while arr[r+dx[dir]][c+dy[dir]] != 0:
                dir = (dir - 1) % 4
            # 재귀 호출
            clean(r+dx[dir], c+dy[dir])
            return
    # 청소 안한 칸이 없다면
    else:
        # 후진 가능하면 후진하고 재귀
        nx = r-dx[dir]
        ny = c-dy[dir]
        if arr[nx][ny] != 1:
            clean(nx, ny)
        # 벽이면 리턴
        else:
            return


clean(r, c)
print(cnt)