[python]백준 14503 풀이

로봇 청소기

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

출력

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

풀이

기본적으로 구현 알고리즘은 문제에서 요구하는 요구사항을 모두 구현하기만 하면 정답을 구할 수 있도록 설계되어있습니다. 이 문제도 마찬가지입니다. 다만, 현재 로봇청소기가 바라보는 방향에 맞추어 방향 벡터를 설정해야 문제풀이가 편하고, 현재 바라보는 방향이 청소가 되지 않은 상태여도 무조건 한번 반시계방향으로 회전해야 합니다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 0 : 북, 1 : 동, 2 : 남, 3 : 서
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
result = 0
while True:
    if graph[r][c] == 0:
        graph[r][c] = 2
        result += 1

    # 주변 칸의 청소상태 스캔
    cnt = 0
    for i in range(4):
        if graph[r+dy[i]][c+dx[i]] != 0:
            cnt += 1
    
    # 청소할 수 없다면
    if cnt == 4:
        nr, nc = r-dy[d], c-dx[d]
        # 벽이라면 종료
        if graph[nr][nc] == 1:
            break
        # 후진 가능하면 이동
        else:
            r, c = nr, nc
    
    # 청소할 수 있다면
    else:
        # 반시계 방향으로 회전
        for i in range(4):
            d -= 1
            if d < 0:
                d = 3
            # 청소해야 하는 칸이 등장하면 이동 후 회전 종료
            nr, nc = r+dy[d], c+dx[d]
            if graph[nr][nc] == 0:
                r, c = nr, nc
                break
print(result)