백준 20010 악덕 영주 혜유

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/20010

이 문제는 최소 스패닝 트리를 구하고, 최소 스패닝 트리 안에서 두 마을을 대상으로 가장 먼 거리를 구하는 문제이다.

풀이

난이도 : GOLD II

문제 풀이는 크루스칼 알고리즘과 DFS 를 이용하여 풀이하였다.

이 문제는 전체 마을을 연결하는 최소 비용과 그 안에서 비용이 가장 큰 두 마을의 이동 비용를 구해야 한다.

첫 번째로 전체 마을을 연결하는 최소 스패닝 트리를 구하는 방법으로 크루스칼 알고리즘을 사용하였다.
가장 작은 cost 부터 union-find 를 수행하였고, union 할 때 그래프 정보를 기록하였다.

두 번째로 두 마을을 구하기 위해서 수행한 과정은 다음과 같다,
1) 임의의 점에서 dfs 를 한 번 수행하여 최소 스패닝 트리에서의 꼭짓점을 모두 구해주기
2) 위에서 구한 각 꼭짓점들에서 출발하여 dfs 를 수행하며 모든 비용 기록
3) 기록한 비용 중 가장 큰 값 출력

코드

import sys

input = sys.stdin.readline

# 그래프의 끝으로 이동하여 ends 에 기록
def dfs_end(x, visited):
    isEnd = True
    for next, dist in graph[x]:
        if visited[next]:
            continue
        
        isEnd = False
        visited[next] = True
        end = dfs_end(next, visited)
        visited[next] = False
    
    if isEnd:
        ends.append(x)

# dfs 로 이동하며 cost 를 기록
def dfs_check(x, visited, cost):
    max_cost.append(cost)
    for next, dist in graph[x]:
        if visited[next]:
            continue

        visited[next] = True
        dfs_check(next, visited, cost + dist)
        visited[next] = False

# 유니온 파인드
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = parent[a]
    else:
        parent[a] = parent[b]

n, k = map(int, input().split())
parent = [i for i in range(n + 1)]
graph = [[] for _ in range(n + 1)]
edges = []

for _ in range(k):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

# 크루스칼
edges = sorted(edges)

result = 0
for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        result += cost
        graph[a].append((b, cost))
        graph[b].append((a, cost))
        union_parent(parent, a, b)

# 전체 마을 연결 최소 비용 출력
print(result)

# 크루스칼로 완성한 그래프에서 끝 점들과 cost 목록을 담을 변수
ends = []
max_cost = [0] * (n + 1)

# dfs visited
visited = [False] * (n + 1)
visited[0] = True

# graph 상의 끝 점들 기록
dfs_end(0, visited)

# 끝 점들로부터 출발하여 cost 기록
visited[0] = False
for end in ends:
    dfs_check(end, visited, 0)

# 마을과 마을 사이의 가장 큰 경로의 비용 출력
print(max(max_cost))