[Python] 백준 / gold / 1261 : 알고스팟

문제 링크 : https://www.acmicpc.net/problem/1261

얼핏 보면 DFS 나 BFS 문제로 보인다. 근데 각 칸을 노드로 생각해서 다익스트라 알고리즘을 사용하면 풀리는 문제다. 간선의 가중치를 0, 1로 설정하면 된다.

3가지를 얻어가면 될 것 같다.

1. 거리가 0인 간선이 있어도 다익스트라는 수행이 된다.
2. heapq 를 이용한 O(E*logV) 알고리즘으로 풀기 위해서는 distance table 과 탐색중인 dist 를 비교해서 continue 하는 과정을 잊지 말아야 한다.
3. 그래프 문제여도, "아주 가끔" 다익스트라로 풀리는 경우도 있다.

파이썬 코드

import sys
import heapq
M, N = map(int, sys.stdin.readline().split())
graph = []
INF = 987654321
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우

for _ in range(N):
    input = sys.stdin.readline().strip()
    a = []
    for x in input:
        a.append(int(x))
    graph.append(a)


def adjacent(x, y):
    nodes = []
    for d in direction:
        nx = x + d[0]
        ny = y + d[1]
        if 0 <= nx < N and 0 <= ny < M:
            nodes.append((nx, ny))
    return nodes


# 다익스트라
distance = [[INF]*M for _ in range(N)]
distance[0][0] = 0

q = []

for x, y in adjacent(0, 0):
    # 최단거리 테이블 세팅
    distance[x][y] = graph[x][y]
    # 힙에 푸시. 거리, 노드 좌표
    heapq.heappush(q, (graph[x][y], x, y))

while q:
    d, x, y = heapq.heappop(q)
    # 중복처리 차단
    if distance[x][y] < d:
        continue

    for nx, ny in adjacent(x, y):
        cost = d + graph[nx][ny]
        if cost < distance[nx][ny]:
            distance[nx][ny] = cost
            heapq.heappush(q, (cost, nx, ny))

print(distance[-1][-1])