[백준] 다익스트라 (1261번)

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

1261번: 알고스팟

다익스트라

 

다익스트라 알고리즘은 그래프에서 간선 비용이 0 또는 양수일 때 그리고 시작 지점이 주어졌을 때 최소 비용 거리를 찾기에 유용한 알고리즘입니다.

 

원리는 간단합니다. (하지만 까먹습니다.)

 

1. 현재 노드에서 이동할 수 있는 후보 노드들을 조건을 따져 등록합니다.

2. 후보 노드들 중 비용이 가장 적은 노드로 이동합니다. (따라서 heap queue가 유용합니다)

3. current 노드가 이미 최소 비용이 아닐 경우는 패스합니다.

4. 위 과정을  반복합니다.

 

 

다음은 문제 풀이 코드입니다.

import sys
import heapq

m, n= map(int, sys.stdin.readline().split())

INF = int(1e9)

board = []

for _ in range(n):
    row = list(map(int, list(sys.stdin.readline().rstrip())))
    board.append(row)

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

distance = [[INF for _ in range(m)] for _ in range(n)]	# 비용

q = [(0, 0, 0)]         # (w, x, y)

heapq.heapify(q)
distance[0][0] = 0
									# (1)
while q:
    current = heapq.heappop(q)

    w, x, y = current[0], current[1], current[2]

    if w > distance[x][y]:		# (2)
        continue

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

        if nx < 0 or nx >= n or ny < 0 or ny >= m:		#(3)
            continue

        d = distance[x][y] + board[nx][ny]

        if d < distance[nx][ny]:			#(4)
            distance[nx][ny] = d
            heapq.heappush(q, (d,nx,ny))
            
print(distance[n-1][m-1])

 

 

#(1) : 번호의 위 쪽은 초기 세팅입니다. 시작지점이 (1, 1) 이므로 (0, 0) 으로 설정하고 자기 자신으로 가는 비용은 0이므로 0으로 설정해줍니다.

#(2) : current는 현재 노드를 의미합니다. 현재 노드에 오기 전에 다른 노드에서 비용을 업데이트 했을 경우를 체크해줍니다. (만약 다른 노드에서 이미 더 적은 비용으로 현재 노드를 방문했다면 현재 노드를 확인하지 않습니다.)

#(3) : nx는 다음에 갈 후보 노드입니다. 다음 노드가 index를 벗어나지 않도록 합니다.

#(4) : d는 현재 노드에서 다음 노드를 갈 때 비용을 말합니다. distance는 실제로 이동했을 때 최소 비용을 의미합니다. 따라서 현재 노드에서 다음 노드로 가는 비용이 최소 비용보다 적을 경우에 큐에 push 합니다.

만약 최소 비용보다 적을 경우 distance를 업데이트 해주고 큐에 push 해줍니다.