[다익스트라] 백준 266번: 미로만들기 / 골드 4

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

2665번: 미로만들기

import heapq

n = int(input())
table = []
for _ in range(n):
    table.append([int(x) for x in input()])

visited = []
for _ in range(n):
    visited.append([False for _ in range(n)])


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

q = []
start = [0, 0, 0]  # crush, x, y
visited[0][0] = True
heapq.heappush(q, start)

while q:
    crush, x, y = heapq.heappop(q)
    print(crush, x, y)

    if x == n-1 and y == n-1: #finish
        print(crush)
        quit()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
            visited[nx][ny] = True

            if table[nx][ny] == 0: # black room
                heapq.heappush(q, [crush+1, nx, ny])
            elif table[nx][ny] == 1: # white
                heapq.heappush(q, [crush, nx, ny])

전형적인 다익스트라 문제!

crush(=충돌 횟수)로 우선순위 큐를 만들어 bfs 탐색을 해주면 된다.