[BOJ/백준] 11085 군사이동

import heapq
import sys
input = sys.stdin.readline
def find_parents(X):
    if make_set[X] ==X:
        return X
    else:
        make_set[X] = find_parents(make_set[X])
        return make_set[X]
 
 
def union(a,b):
    X = find_parents(a)
    Y = find_parents(b)
    if X == Y:
        return False
    if rank[X]< rank[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if rank[X] == rank[Y]:
        rank[X] += 1
    return True
 
 
P,W = map(int,input().split())
 
c,v = map(int,input().split())
 
weight_list = [list(map(int,input().split())) for _ in range(W)]
make_set = [i for i in range(P)]
weight_list.sort(key=lambda x : x[2])
rank = [1 for _ in range(P)]
result = float('inf')
while find_parents(c) != find_parents(v):
    node_a,node_b,pay = weight_list.pop()
    if union(node_a,node_b):
        result = pay
 
 
print(result)

  이 문제를 푸는 방식은 다음과 같다. 최대 길이를 구하고, 그때의 최소 너비를 구하면 되는 것이다.

 

그러므로 크루스칼 알고리즘대로 푸는 대신 가장 앞에서부터 pop을 하던것에서 가장 뒤에서부터 pop을 하면서

 

그 두 노드가 같은 집합이 아닐때 합쳐주면서 그때의 pay를 result에 저장해주면 되는 방식으로 풀면 된다.

 

 

 
import sys
import heapq
 
 
input = sys.stdin.readline
 
P,W = map(int,input().split())
 
start_city,end_city = map(int,input().split())
 
graph = [{} for i in range(P)]
 
for _ in range(W):
    x,y,pay = map(int,input().split())
    graph[x][y] = max(graph[x].get(y,0),pay)
    graph[y][x] = max(graph[y].get(x,0),pay)
 
 
max_width_list = [0]*P
max_width_list[start_city] = float('inf')
 
node_list = []
 
heapq.heappush(node_list,(-float('inf'),start_city))
 
 
while node_list:
    maximun_width,cur_node  = heapq.heappop(node_list)
    maximun_width = -maximun_width
    for next_node in graph[cur_node]:
        
        cur_maximun_width = min(graph[cur_node][next_node],maximun_width)
 
        if cur_maximun_width > max_width_list[next_node]:
            max_width_list[next_node] = cur_maximun_width
            heapq.heappush(node_list,(-max_width_list[next_node],next_node))
 
 
print(max_width_list[end_city])

 

 

프림 알고리즘으로 푸는 방식은 거의 동일하다. 대신 cur_maximun_width가 다른데, 현재의 간선의 너비와 지금까지 최대 간선의 너비와 비교해서

 

그 중 더 큰 값을 비교에 쓴다.

 

이 점만 주의하고, 최소힙이 아니라 최대힙을 사용하면 해당 문제를 풀 수 있다.