[Python/BOJ] 20010. 악덕 영주 혜유

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

20010번: 악덕 영주 혜유

 

문제

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 사이의 번호를 갖는다.

출력

첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다. 

두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다.

풀이

Code

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

def solution(n, k, costs) :
    global max_distance
    # 1. Union 함수 정의
    def Union(x, y) :
        # 1-1. x, y의 루트 노드 찾기
        x = Find(x)
        y = Find(y)
        # 1-2. x > y 의 경우 루트 노드 정보 입력
        if x > y : roots[x] = y
        # 1-3. 이외의 경우 루트 노드 정보 입력
        else : roots[y] = x
    # 2. Find 함수 정의
    def Find(x) :
        # 2-1. 해당 노드가 루트 노드가 아닐 경우
        if x != roots[x] : return Find(roots[x])
        # 2-2. x 반환
        return x
    # 3. DFS 함수 정의
    def dfs(node, visited, dist) :
        global max_distance
        # 3-1. 최대 거리 업데이트
        if dist > max_distance :
            max_distance = dist
        # 3-2.
        for next, c in route[node] :
            # 방문하지 않았을 경우
            if not visited & (1 << next) :
                # dfs 실행
                dfs(next, visited | (1 << next), dist + c)

    # 4. 비용을 기준으로 오름차순 정렬
    costs.sort(key = lambda x : x[2])
    # 5. 루트 노드 리스트 생성
    roots = list(range(n+1))
    # 6.
    distance = 0
    route = defaultdict(list)
    for x, y, cost in costs :
        # 6-1. 사이클 테이블 확인
        if Find(x) != Find(y) :
            # 경로 추가
            route[x].append((y, cost))
            route[y].append((x, cost))
            # 거리 추가
            distance += cost
            Union(x, y)
    # 7. dfs 실행
    for start in route.keys() :
        # 7-1. DFS 실행
        dfs(start, (1 << start), 0)
    # 8. 결과 출력
    print(distance)
    print(max_distance)

if __name__ == "__main__" :
    n, k = map(int, input().split())
    costs = [list(map(int, input().split())) for _ in range(k)]
    max_distance = -int(1e9)
    solution(n, k, costs)