[백준(파이썬/Python)] 2665_미로만들기 - BFS, 우선순위 큐

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

2665번: 미로만들기

 

얼마 전에 풀었던 백준 1261번(알고스팟, https://www.acmicpc.net/problem/1261) 문제와 동일하게 풀 수 있었던 문제입니다.

 

BFS와 우선순위 큐를 이용하는데, 검은 방에서 흰 방으로 바꾸는 횟수를 최소화해야 하므로 우선순위 큐의 첫번째 원소를 '지금까지 흰색으로 바꾼 검은 방의 갯수'로 지정해주면 됩니다.

 

이렇게 하는 이유는 매번 우선순위 큐에서 원소를 뽑을 때마다 벽을 바꾼 횟수가 최소인 지점부터 뽑을 수 있고, 그 지점을 기준으로 상하좌우를 탐색해 나가기 때문입니다. 그러면 결과적으로 벽을 바꾼 횟수가 최소이면서, 도착점까지 갈 수 있겠죠.

 

이 부분을 제외하고는 BFS 풀이와 동일합니다.

 

[풀이]

import sys, heapq

def bfs(x, y):
    visited = [[False] * n for _ in range(n)]   # 방문을 체크할 리스트
    pq = []
    heapq.heappush(pq, (0, x, y))
    while pq:
        count, curr_x, curr_y  = heapq.heappop(pq)
        
        # 끝에 도달하면 결과값 리턴
        if curr_x == n-1 and curr_y == n-1:
            return count

        for i in range(4):
            next_x, next_y = curr_x + dx[i], curr_y + dy[i]
            if 0 <= next_x < n and 0 <= next_y < n and not visited[next_x][next_y]:
                # 검은 방인 경우 흰 방으로 바꾼다.
                if graph[next_x][next_y] == 0:
                    heapq.heappush(pq,(count+1, next_x, next_y))
                else:
                    heapq.heappush(pq,(count, next_x, next_y))
                visited[next_x][next_y] = True
        

input = sys.stdin.readline
n = int(input())
graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

# 결과 출력하기
print(bfs(0,0))