다익스트라를 응용해서 minimum bottleneck path 문제 기본 배우기

1. 문제

 

23286번: 허들 넘기 (acmicpc.net)

23286번: 허들 넘기

 

2. 풀이

 

출발 정점에서 도착 정점으로 가는 길에 가중치가 가장 큰 간선의 가중치가 최소가 되는 경로를 찾는 문제

 

경로에서 가중치가 가장 큰 간선을 bottleneck path라고 부른다

 

이 bottleneck path의 가중치를 최소로 만드는 문제가 minimum bottleneck path problem

 

여러가지 방법이 있는것 같기는 한데.. 가장 기본은 다익스트라 알고리즘을 살짝 변형하면 된다

 

1) distance[i]를 "시작정점에서 정점 i까지 가는 경로에서 bottleneck path의 최소 가중치"라고 정의

 

최소라고 정의했으니 distance = [INF]*(n+1)로 초기화

 

2) 시작정점의 minimum bottleneck path = 0으로 시작하고, 우선순위 큐에 (cost = 0, 시작정점)을 넣는다

 

3) 우선순위 큐에서 cost, 정점을 하나 빼서, 현재 정점의 minimum bottleneck path인 distance[정점]이 cost와 다르다면, continue

 

4) distance[정점]과 cost가 같다면, 갱신을 위해 정점과 연결된 간선 (가중치, 정점)을 모두 순회해서,

 

여기서 cost = max(가중치, cost)로 갱신해준다.

 

여기가 다익스트라 알고리즘과는 다른 포인트

 

다익스트라 알고리즘은 현재 정점에서 다음 정점으로 이동하면서 매 순간 가중치 합이 가장 작도록 갱신해간다면,

 

minimum bottleneck path 알고리즘은 다음 정점으로 이동하면서 매 순간 가중치가 가장 큰 path를 찾아야하니, cost를 max(가중치)로 갱신해준다.

 

5) distance[정점]은 "해당 정점에 도달하면서 거친 최대 가중치 값의 최솟값"이므로,

 

distance[정점] > cost이면, distance[정점] = cost로 갱신해주고, 갱신이 된다면 우선순위 큐에 (cost, 정점)을 넣어준다

 

#다익스트라를 이용한 minimum bottleneck path 알고리즘

import heapq
from sys import stdin

INF = 10000000000000000000000000

def dijkstra(start):
    
    queue = []

    heapq.heappush(queue,(0,start))

    distance = [INF]*(n+1) #"정점 i로 도착하는 동안 탐색한 최대 가중치의 최솟값"

    distance[start] = 0

    while queue:
        
        h,u = heapq.heappop(queue)

        if distance[u] != h:
            
            continue
        
        for v,c in graph[u]:
            
            cost = max(h,c) #경로를 탐색하면서, cost는 경로 가중치가 최대인 값으로 갱신
            
            #최대 가중치의 최솟값이 더 작아진다면, 갱신해준다
            if  distance[v] > cost:

                distance[v] = cost
                heapq.heappush(queue,(cost,v))
    
    return distance

 

 

근데 이 문제는 쿼리 문제인데..

 

매 쿼리마다 반복적으로 다익스트라 알고리즘을 수행하면 시간 초과를 받을게 뻔하니까,

 

쿼리에 답하기 전에 모든 정점 1~n에 대해 알고리즘을 미리 수행해놓고, 얻은 distance를 저장해둔다

 

그리고 u,v를 받으면 u를 시작점으로 하는 distance는 이미 구해놨으니까, O(1)에 바로 답하면 된다.

 

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

graph = [[]*(n+1) for _ in range(n+1)]

for _ in range(m):
    
    u,v,h = map(int,stdin.readline().split())

    graph[u].append((v,h))

#모든 정점에 대해 minimum bottleneck path를 구해놓은 배열을 미리 계산
dist = [0]

for i in range(1,n+1):
    
    dist.append(dijkstra(i))

#미리 계산해놓은 배열을 이용해 쿼리에 O(1)에 답해주기
for _ in range(t):
    
    u,v = map(int,stdin.readline().split())

    if dist[u][v] == INF:
        
        print(-1)
    
    else:
        
        print(dist[u][v])