[백준/최소신장트리] 20010번 악덕 영주 혜유

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

20010번: 악덕 영주 혜유

 

문제를 요약하면 양방향 이동 가능한 길을 통해, 도달이 불가능한 마을이 없도록 길을 만드는 것이다.

 

구해야하는 답은,

1. 마을을 연결하는 최소의 비용 계산
2. 마을과 마을을 이동하는 가장 최악의 비용 계산

 

1번. 최소한의 비용으로 연결하기 위해 최소 신장 트리 (minumum spanning tree)를 사용했다.

1. 간선을 비용이 적은 순으로 정렬 시킨다.
2. 적은 순서 부터 길을 확정한다. 확정하기 위해서는
   1) 가려는 노드와 현재 노드의 root 가 같으면 회전이 되서 안된다. 그러므로 root를 확인한다.
   2) Root가 다르면, 그 길을 확정하고 , 두 노드가 연결되었으므로 두 노드의 Root를 같은 것으로 만든다.

 2번. 결정된 길에서 최악의 길의 비용 구하기

이를 위해 1번에서 길을 확정할 때, 그 길들을 따로 저장한다.

그리고 끝에서 끝으로 연결된 것들만 볼 것이므로, 연결된 길이 1개인 노드들만을 시작점으로한다.

BFS를 통해 최대 길이를 찾는다.

 

 

import sys
from collections import deque

input = sys.stdin.readline

N,M=map(int,input().split())

root = [i for i in range(N)]
edge = [list(map(int,input().split())) for _ in range(M)]

#비용이 가장 적은 순으로 나열
edge.sort(key = lambda x:x[2])

#root를 계속 찾기
def find(x):
    if x!= root[x]:
        root[x] = find(root[x])

    return root[x]

ans = 0
adj = [[] for _ in range(N)]

for s,e,w in edge:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot!=eRoot:
        if sRoot>eRoot:
            root[sRoot] = eRoot
        else:
            root[eRoot] = sRoot
        adj[s].append((e,w))
        adj[e].append((s,w))
        ans += w
        
#BFS
max_ans = 0
for i in range(N):
    if len(adj[i]) == 1: #끝에서 끝이므로, 연결된 노드가 하나인 것만 확인
        visit = [False] * N
        q = deque([(i,0)])
        visit[i] = True

        temp = 0

        while q:
            now, dist = q.pop()
            temp = max(dist,temp)
            for go, w in adj[now]:
                if not visit[go]:
                    visit[go] = True
                    q.appendleft((go,dist+w))

        max_ans = max(temp,max_ans)
        

print(ans)
print(max_ans)