[악덕 영주 혜유/G2/Python3]

20010번 악덕 영주 혜유 G2

 

문제
FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, 교역로는 양 방향으로 이동할 수 있으며, 서로 도달이 불가능한 마을이 없도록 교역로를 건설하여야 한다. 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 폐유를 도와서 모든 마을과 마을을 최소한의 비용으로 연결하고 그 비용을 구해보자. 또한 혜유는 이때 마을과 마을을 이동하는 가장 최악의 비용이 얼마인지에 관심이 많다. 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용도 구해보자.

입력
첫 번째 줄에는 마을의 수 N(1 ≤ N ≤ 1,000)과 설치 가능한 교역로의 수 K(1 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 줄부터 K + 1줄에는 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c가 주어진다. (1 ≤ c ≤ 1,000,000) 항상 모든 마을을 연결할 수 있는 경우만 입력으로 주어진다, 또한 최소 비용으로 연결하는 방법은 유일하다. 서로 다른 두 마을 사이에 건설할 수 있는 교역로는 최대 하나뿐이다. 마을은 0부터 N - 1 사이의 번호를 갖는다.

출력
첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다.
두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다.

 

 

그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최소 스패닝 트리

 

MST + 트리의 지름 알고리즘을 사용했다.

크루스칼 알고리즘으로 간선들을 연결하고 해당 간선을 저장하였다.

저장한 간선을 통해 DFS를 돌려 트리의 지름을 구했다.

 

import sys

n, m = map(int, sys.stdin.readline().split())
p = [i for i in range(n)]

routes=[[] for _ in range(n)]

lines = []
for _ in range(m):
    v1, v2, cost = map(int, sys.stdin.readline().split())
    lines.append((cost, v1, v2))

lines.sort()
result = 0

def find(v):
    if p[v] == v: return v
    p[v] = find(p[v])
    return p[v]

def union(v1, v2, c):
    r1, r2 = find(v1), find(v2)
    p[r1] = r2
    
    routes[v1].append((v2, c))
    routes[v2].append((v1, c))

for c, v1, v2 in lines:
    if find(v1) == find(v2): continue
    union(v1, v2, c)
    result += c

print(result)

distance = 0
max_vertex = 0

def dfs(vertex, value):
    global distance
    global max_vertex
    visit[vertex] = True
    
    for v, w in routes[vertex]:
        if not visit[v]:dfs(v,w+value)
        
    if value >= distance:
        max_vertex = vertex
        distance = value

for i in range(2):
    distance = 0
    visit = [False] * n
    dfs(max_vertex, 0)
print(distance)​

 

---