[Algorithm] 백준 2665 미로만들기 | 파이썬 BFS

※ 2665 미로만들기

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

 

문제 해결 TIP

visited 배열에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 저장한다. bfs로 탐색하면서, 흰 방인 경우를 먼저 탐색한다.(appendleft) 검은 방일 경우에는 이전 visited값에 1을 추가해준다.

 

전체 코드

from collections import deque

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


def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    visited = [[-1] * n for _ in range(n)]
    visited[x][y] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==-1:
                if graph[nx][ny]==1:
                    queue.appendleft((nx,ny))
                    visited[nx][ny] = visited[x][y]
                else:
                    queue.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1
    return visited
graph = []
n = int(input())
for i in range(n):
    graph.append(list(map(int,input())))

visited = bfs(0,0)
print(visited[n-1][n-1])