[BOJ/py] 14503 로봇청소기

문제 링크 https://www.acmicpc.net/problem/14503

📝 문제

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

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

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

💻 코드

def dfs(x, y, d):
    global cnt

    if arr[x][y] == 0:
        arr[x][y] = 9
        cnt += 1

    for k in range(4):
        d = (d + 3) % 4
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
            dfs(nx, ny, d)
            return

    nx = x - dx[d]
    ny = y - dy[d]
    if arr[nx][ny] == 1:
        print(cnt)
        return

    dfs(nx, ny, d)


N, M = map(int, input().split())
x, y, d = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

cnt = 0

dfs(x, y, d)

📌 해결방법

1. 현재 방향을 d라면 반시계 방향으로 회전한 후의 방향은
   (d + 3) % 4 라는 점이 포인트!
2. 현재 방향이 북쪽이라면, 반시계 방향 후 회전 후 한칸 전진한 값은
   현재 방향 + 1의 방향에서 후진한 값과 같음
3. 따라서 4방향 탐색의 방향을 동, 남, 서, 북으로 두고 시작
   dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

✔ 느낀 점

문제의 순서만 따라가면서 코드를 작성하려고 하지 않고, 전체적으로 흐름을 파악한 후에 적절한 코드를 작성하는 것이 필요하다.
처음에는 문제의 입력부분에 나온 인덱스에 따라 북, 동, 남, 서에서 후진한 방향을 기준으로 코드를 작성하였는데 방향을 설정할 때 여러 경우의 수를 작성하여야 했다. 그러다가 결국 문제에서 움직이는 방향은 한정적인것을 생각하고 전진하는 것을 기준으로 코드를 작성하여 여러번의 인덱스 변경 대신에 전진은 x + dx[d], 후진은 x - dx[d] 라는 간결한 식으로 표현할 수 있었다!