[python] 백준 14503 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

문제 해결

• 한칸씩 정해진 규칙대로 움직이면서 청소 안된 곳 청소하는 것으로 구현하는 문제
• 사실 어렵진 않지만 처음 원본 그대로 deepcopy를 해야한다. 그 이유는 처음 0, 1은 단순히 청소 안된 곳, 청소 된 곳을 의미하는 것이 아니라 이동할 수 있는 곳, 이동 할 수 없는 곳(벽)을 의미하는 것이기도 하기 때문이다.
• 따라서 아래 코드는 visited는 이동할 수 있는 곳, 없는 곳을 나타내며 board는 청소 한 곳 안한 곳을 구별하는 그래프이다.

 

CODE

from collections import deque
import copy
n, m = map(int, input().split())
move = [(-1,0), (0,1), (1,0), (0,-1)]
r, c, go = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = copy.deepcopy(board)
def bfs():
    que = deque()
    que.append((r,c,go))
    cnt = 0
    while que:
        x, y, dir = que.popleft()
        if visited[x][y] ==0:
            cnt += 1
            visited[x][y] = 1
        for _ in range(4):
            dir = (dir-1)%4
            new_x = x + move[dir][0]
            new_y = y + move[dir][1]
            if 0> new_x or new_x >n-1 or new_y <0 or new_y >m-1: continue
            if visited[new_x][new_y] ==0:
                que.append((new_x, new_y, dir))
                break
        else:
            if 0<= x - move[dir][0] and x-move[dir][0]<=n-1 and 0<= y-move[dir][1] and y-move[dir][1] <= m-1 and board[x-move[dir][0]][y-move[dir][1]]==0:
                que.append((x-move[dir][0], y-move[dir][1], dir))
            else:
                return cnt
ans = bfs()
print(ans)