[Python/파이썬] 백준 2665번 미로만들기

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

코드

from collections import deque

n = int(input())
rooms = [input() for _ in range(n)]

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

q = deque([(0, 0)])
visited = [[int(1e9)]*n for _ in range(n)]
visited[0][0] = 0
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if rooms[nx][ny] == "0" and visited[nx][ny] > visited[x][y]+1:
                visited[nx][ny] = visited[x][y]+1
                q.append((nx, ny))
            elif rooms[nx][ny] == "1" and visited[nx][ny] > visited[x][y]:
                visited[nx][ny] = visited[x][y]
                q.append((nx, ny))

print(visited[n-1][n-1])

 

일반적인 BFS와 비슷한데, 방문 여부를 기록하던 visited에 방문 여부 대신 해당 칸까지 가는데 바꾸어야 할 방의 최소 개수를 저장하면 된다.