[BOJ/백준] 20010 악덕 영주 혜유 파이썬

문제 링크 : https://www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

MST와 DFS로 풀이 했다.

 

첫번째 답은 모든 마을을 연결하는 최소 비용을 출력해야하므로 MST 로 구한다.

두번째 답은 마을과 마을 사이의 최단 경로 중 비용이 가장큰 경로 이므로 BFS나 다익스트라로 구하면 된다.

 

MST는 크루스칼로 구현했다.

MST를 구성하면서 BFS에서 사용할 그래프를 인접리스트로 저장했다.

 

인접리스트 중 길이가 1인 점에서만 BFS를 수행했다. 끝에서 끝으로 가야 최대일 것이므로 연결된 노드가 하나인 것만 확인하면 된다.

 

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

n,k = map(int, input().split())

edges = [tuple(map(int, input().split())) for _ in range(k)]
edges.sort(key=lambda x:x[2])
parents = [i for i in range(n)]
adj_list = [[] for _ in range(n)]
def solv():
    total_cost = kruskal()
    max_dist = 0

    for start in range(n):
        if len(adj_list[start]) == 1:
            max_dist = max(max_dist, bfs(start))
    print(total_cost)
    print(max_dist)
def bfs(start):
    visited = [False] * n
    q = deque([(start,0)])
    visited[start] = True
    max_dist = 0
    while q:
        now,dist = q.pop()
        max_dist = dist if max_dist < dist else max_dist
        for nxt, cost in adj_list[now]:
            if not visited[nxt]:
                visited[nxt] = True
                q.appendleft((nxt,dist+cost))
    return max_dist
def find(target):
    global parents

    if parents[target] == target:
        return target
    parents[target] = find(parents[target])
    return parents[target]

def union(a, b):
    global parents
    a = find(a)
    b = find(b)

    if a != b:
        parents[a] = b

def is_same_parent(a,b):
    return find(a) == find(b)

def kruskal():
    global adj_list
    edge_count = 0
    cost = 0
    for a,b,c in edges:
        if not is_same_parent(a,b):
            adj_list[a].append((b,c))
            adj_list[b].append((a,c))
            union(a,b)
            edge_count += 1
            cost += c
            if edge_count == n-1:
                return cost
solv()