백준 14503 : 로봇청소기

문제

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

로봇 청소기가 있는 방은 $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번으로 돌아간다.

입력

첫째 줄에 방의 크기 $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)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 1

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1

1

예제 입력 2

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2

57

Sol)

갈 수 있는 경우의 수가 조건에 맞는 1개이면 queue 쓸 필요 없음.
여러 경우의 수 골고루 탐색해야하면 queue 필요함.

이 문제는 왼쪽부터 조건 탐색해서 맞으면 무조건 전진하기 때문에 queue 필요없음.

import sys

input = sys.stdin.readline
N, M = map(int,input().split())

y_s, x_s, d = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]


# 북 동 남 서
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

# direction_dic 정의 -> key : 현재 방향, value : 탐색 순서대로의 다음 방향
direction_dic = {0:{'next_dir':[3,2,1,0]}, # 현재 방향이 '북'일 때, 다음 방향 후보는 '서','남','동','북' 순
                1:{'next_dir':[0,3,2,1]},
                2:{'next_dir':[1,0,3,2]},
                3:{'next_dir':[2,1,0,3]}}

def bfs(y, x, d):

    visited[y][x] = 1

    while True:
        for next_d in direction_dic[d]['next_dir']:
            ny = y + dy[next_d]
            nx = x + dx[next_d]

            if 0 <= ny < N and 0<= nx < M and graph[ny][nx]==0 and visited[ny][nx]==0:
                y, x = ny, nx
                visited[ny][nx] = 1

                d = next_d
                break

        else:
            ny = y + dy[d]*(-1)
            nx = x + dx[d]*(-1)
            y, x = ny, nx
            if graph[ny][nx]==1:
                break

    num = sum([sum(x_axis) for x_axis in visited])
    return num

print(bfs(y_s, x_s, d))

문제에서 현재 위치는 시계방향순으로 정의했는데 agent는 반시계방향순으로 탐색하는 걸로 정의했기 때문에 헷갈릴 수 있음.

인덱스 i=0,1,2,3일 때,
"다음 방향 = ((현재 방향-1)-i)%4" 이라는 관계식을 바로 만들어낼 수 있으면 좀 더 간결한 코드가 되었겠으나 굳이 이를 찾기 위해 시간을 쏟을 것 같으면 내가 푼 것처럼 딕셔너리로 경우의 수 관리하면 좀 더 심플하게 풀 수 있음.