[알고리즘] Dijkstra

다익스트라 알고리즘

최단경로 알고리즘
특히 가중치가 있는 경우 유용하다

모든 정점이 출발지에서 도착지로 갈 수 있다는 가정하에
O(V^2) -> 우선순위 큐를 사용해 O(E logV)

python에서는 최소 heap을 이용해 구현하면 된다

백준 4485 녹색 옷 입은 애가 젤다지?

시간초과 - visited로 재방문 방지

import sys
input = sys.stdin.readline
import heapq

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

while True:
    problem += 1
    n = int(input())
    if n == 0:
        break
    
    graph = [list(map(int, input().split())) for _ in range(n)]
    visited = [[False]*n for _ in range(n)]
    
    q = []
    # cost, x, y
    heapq.heappush(q, (graph[0][0], 0, 0))
    
    while q:
        cost ,x, y = heapq.heappop(q)
        visited[x][y] = True
        
        if x == n-1 and y == n-1:
            print(f"Problem {problem}: {cost}")
            break
        
        for i in range(4):
            xx, yy = x + dx[i], y+dy[i]
            if 0<=xx<n and 0<=yy<n and not visited[xx][yy]:
                heapq.heappush(q, (cost+graph[xx][yy], xx, yy))

성공 - distance로 비교해서 재방문 방지
방문하지 않은 node의 비용은 inf
방문할 때 기존 비용보다 작다면 비용을 update

import sys
input = sys.stdin.readline
import heapq

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

while True:
    problem += 1
    n = int(input())
    if n == 0:
        break
    
    graph = [list(map(int, input().split())) for _ in range(n)]
    distance = [[int(1e9)]*n for _ in range(n)]

    q = []
    # cost, x, y
    heapq.heappush(q, (graph[0][0], 0, 0))
    
    while q:
        cost ,x, y = heapq.heappop(q)
        
        if x == n-1 and y == n-1:
            print(f"Problem {problem}: {cost}")
            break
        
        for i in range(4):
            xx, yy, ncost = x + dx[i], y+dy[i], cost + graph[x][y]
            if 0<=xx<n and 0<=yy<n and ncost<distance[xx][yy]:
                distance[xx][yy] = ncost
                heapq.heappush(q, (cost+graph[xx][yy], xx, yy))

bfs와 살짝 섞어서 마음대로 풀었더니 시간초과가 발생했다

visited로 했을 때 시간초과가 나는 이유

완전 적절한 예시는 아니지만 distance로 했을 때
큐에 불필요한 값이 들어가지 않는다
언뜻 생각했을 때는 같은 node에 중복탐색을 허용하면 탐색을 더 많이 하는거 아닌가? 생각이 들었지만 직접 해보니 OK

컴공스러운 문제 설명을 읽는게 재미있었다

백준 5972 택배 배송

import sys
input = sys.stdin.readline
from collections import defaultdict
import heapq

n, m = map(int, input().split())
dic = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    dic[a].append((b, c))
    dic[b].append((a, c))
    

q = []
heapq.heappush(q, (0, 1))

dist = [int(1e9)] * (n+1)

while q:
    cost, node = heapq.heappop(q)
    if node == n:
        print(cost)
        break
    for next_node, next_cost in dic[node]:
        if cost + next_cost < dist[next_node]:
            heapq.heappush(q, (cost+next_cost, next_node))
            dist[next_node] = cost + next_cost

가장 기본적인 문제

위 문제와 같이 visited / distance로 계산하는 코드로 비교해 봤는데
약 1.7배로 꽤 큰 차이가 난다