[Python] 백준 14503번 로봇 청소기

문제

14503번: 로봇 청소기

입력

• 첫째 줄에 방의 크기 N과 M이 입력된다. 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽, 1인 경우 동쪽,2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.
• 셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i,j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

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

입력 예제

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

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

출력 예제

1

57

문제 풀이

• board의 값을 2로 바꾸면서 방문 처리
• 반시계 방향으로 차례대로 회전하면서 청소되지 않은 칸이 있다면, 방문처리 하고, 큐에 넣는다.
• 이 때 현재 바라보고 있는 칸의 회전은 종료하고, 큐에 넣은 좌표들을 회전 시키며 새로 탐색을 해야 하므로 break문을 써서 for문을 빠져나와야 함 !!!
• 근처에 청소되지 않은 칸이 없다면 뒷 칸이 벽이 아닌 경우 후진하고, 뒷 칸이 벽이라면 청소를 종료하고 청소한 칸의 수를 반환한다.

코드

from collections import deque
# 북동남서
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
n, m = map(int,input().split())
board = []
y, x, d = map(int,input().split())
for _ in range(n):
    board.append(list(map(int,input().split())))

def turn_left(d):
    return (d + 3) % 4

def bfs(y,x,d):
    cnt = 1
    queue = deque()
    queue.append((y,x,d))
    board[y][x] = 2
    while queue:
        y, x, d = queue.popleft()
        # 반시계 방향으로 회전하면서 청소되지 않은 칸 찾기
        direction = d
        for i in range(4):
            direction = turn_left(direction)
            ny = y + dy[direction]
            nx = x + dx[direction]
            # 앞쪽 칸이 청소되지 않았다면 한 칸 전진
            if 0 <= ny < n and 0 <= nx < m and board[ny][nx] == 0:
                board[ny][nx] = 2
                cnt += 1
                queue.append((ny, nx, direction))
                # 현재 방향 탐색 종료, 1번으로 돌아가기
                break

            else:
                if i == 3:
                    ny = y - dy[direction]
                    nx = x - dx[direction]
                    if board[ny][nx] != 1:
                        queue.append((ny, nx, direction))
                    if board[ny][nx] == 1:
                        return cnt

print(bfs(y,x,d))