[백준] 2665. 미로 만들기 풀이 (Python)

접근한 방법

미로에서 최단 경로를 찾는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 최소 heap 자료구조를 이용하여 매 방문마다 가장 적게 벽을 바꾼 지점의 좌표를 꺼내서 해당 좌표에서만 탐색을 나아가면 최소 개수로 벽을 바꿀 수 있습니다.

 

1. 큐에서 원소를 하나씩 꺼내면서 해당 위치의 상하좌우를 체크합니다.

2. 벽이 있는 경우는 +1 카운트 하여 큐에넣고 그렇지 않은 경우는 그대로 큐에 넣어줍니다.

3. 마지막 지점에 닿으면 현재까지의 카운트를 출력하고 종료합니다.

 

Python

import sys
input = sys.stdin.readline

n = int(input())
arr = list(list(map(int, input().rstrip())) for _ in range(n))

from heapq import heappush, heappop
hq = []
heappush(hq, (0, 0, 0))
visited = [[0] * n for _ in range(n)]
dist = ((-1, 0), (1, 0), (0, -1), (0, 1))

while hq:
    cnt, r, c = heappop(hq)
    if [r, c] == [n - 1, n - 1]:
        print(cnt)
        break
    for d in dist:
        dr, dc = r + d[0], c + d[1]
        if dr < 0 or dc < 0 or dr >= n or dc >= n:
            continue
        if not visited[dr][dc]:
            heappush(hq, (cnt if arr[dr][dc] else cnt + 1, dr, dc))
            visited[dr][dc] = 1