[Python] 백준 1261 : 알고스팟

어려워보이지만, 결국은 Dijkstra

0은 빈칸, 1은 벽이다. 좌측 상단에서 우측 하단으로 이동할 때, 최소한의 벽을 파괴하고 도달해야 한다. 이 문제는 잘 살펴보면 Dijkstra 문제이다. (x좌표, y좌표, 뚫은벽 개수) tuple을 queue에 넣어 관리하면서 최소로 벽을 뚫어나가면 되는 것.

 

정답코드

import heapq
import sys

M, N = map(int, input().split())

graph = []
for i in range(N) :
    row = []
    a = input()
    for j in range(M) :
        row.append(int(a[j]))

    graph.append(row)

visited = [[False] * M for _ in range(N)]
distance = [[sys.maxsize] * M for _ in range(N)]
distance[0][0] = 0

queue = [(0, 0, 0)] 
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

while queue : 

    c_cost, cx, cy = heapq.heappop(queue) 

    if visited[cx][cy] :
        continue

    if cx == N-1 and cy == M-1 :
        print(c_cost)
        break

    visited[cx][cy] = True

    for i in range(4) :
        nx = cx + dx[i]
        ny = cy + dy[i]

        if 0 <= nx < N and 0 <= ny < M :
            if graph[nx][ny] == 1 :
                cost = c_cost + 1
            else : 
                cost = c_cost
            
            if cost < distance[nx][ny] :
                distance[nx][ny] = cost
                heapq.heappush(queue, (cost, nx, ny))