BOJ 20010 - 악덕 영주 혜유 링크
(2023.04.07 기준 G2)

문제

N개의 도시와 K개의 도시끼리 잇는 교역로가 주어질 때, 최소한의 비용으로 모든 마을을 연결하고 그 비용을 출력 및 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용 출력

알고리즘

첫번째는 MST, 두번째는 DFS.

풀이

첫번째 출력은 쉽다. 그냥 간선의 비용이 오름차순이 되게끔 간선 정렬 후 크루스칼 돌리면 된다. 아 물론, 프림도 된다.

두번째가 좀 어려울 수 있다.
잘 생각해보자. 아무 정점에서 제일 먼 정점을 찾아보자. 찾은 정점에서 다시 제일 먼 정점을 찾아보자. 찾은 두 정점 사이의 거리가 트리의 지름이 된다. 즉, 이 문제에서 원하는 답이 나온다.
설명하기 좀 어려운데, 아무 정점을 오른손으로 잡고 나머지 정점을 전부 왼쪽으로 땡긴다고 생각해보자. 그러면 가장 멀리 떨어진 정점이 나올 것이다.
그 멀리 떨어진 정점을 잡고 다시 나머지를 반대쪽으로 전부 땡겨보자. 그럼 또 멀리 떨어진 정점이 나올 것이다. 상상을 해보면 머리로는 바로 이해가 갈 것이다. 찾은 두 정점이 트리의 지름을 이루는 두 정짐이라는 것을. 트리의 임의의 두 정점의 경로는 단 하나라서 모순이 생기지 않는다.

음.. 근데, 이 문제는 가장 먼 경로를 구할 때 일일이 구해도 통과한다는 말이 있던데..

코드

• C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

vector<pii> graph[1000]; // 마을(MST)
vector<tiii> edges;
vector<int> parent(1000);

bool cmp(tiii a, tiii b){
    return get<2>(a) < get<2>(b);
}

int find(int u){
    if (parent[u] != u) parent[u] = find(parent[u]);
    return parent[u];
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    if (u < v) parent[v] = u;
    else parent[u] = v;
}

pii dfs(int u, int p){
    pii result = {0, u}, dfs_result; // 현재 제일 먼 정점까지의 거리와 그 정점
    for (auto vw: graph[u]){
        if (vw.first == p) continue;
        dfs_result = dfs(vw.first, u);
        if (result.first < dfs_result.first + vw.second) result = {dfs_result.first + vw.second, dfs_result.second};
    }
    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;

    int a, b, c;
    for (int i = 0; i < K; i++){
        cin >> a >> b >> c;
        edges.push_back({a, b, c});
    }
    sort(edges.begin(), edges.end(), cmp); // 간선 정렬

    int u, v, w, min_cost = 0, ct = 0; // u, v, w, 최소 비용, 연결된 간선 수
    iota(parent.begin(), parent.begin() + N, 0); // 부모 노드
    for (auto edge: edges){
        u = get<0>(edge);
        v = get<1>(edge);
        w = get<2>(edge);
        if (find(u) != find(v)){ // 부모 노드가 다르면 union
            graph[u].push_back({v, w}); // 간선 연결
            graph[v].push_back({u, w});
            merge(u, v);
            min_cost += w;
            ct += 1;
            if (ct == N - 1){ // 연결된 간선 수가 N - 1개면 MST 완성이므로 중지
                cout << min_cost << '\n';
                break;
            }
        }
    }

    pii result = dfs(0, -1); // 먼저 0번에서 가장 먼 노드를 찾고
    result = dfs(result.second, -1); // 찾은 노드에서 가장 먼 노드까지의 거리가 트리의 지름이 된다.
    cout << result.first;
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

def dfs(u, p):
    result = (0, u) # 현재 제일 먼 정점까지의 거리와 그 정점
    for v, w in graph[u]:
        if v == p:
            continue
        dist, far = dfs(v, u)
        result = max(result, (dist + w, far))
    return result

N, K = map(int, input().split())
edges = sorted([list(map(int, input().split())) for _ in range(K)], key = lambda x: x[2]) # 간선 정렬

graph = [[] for _ in range(N)] # 마을(MST) 구축
parent = [i for i in range(N)] # 부모 노드
min_cost = ct = 0 # 최소 비용, 연결된 간선 수
for u, v, w in edges:
    if find(u) != find(v): # 부모 노드가 다르면 union
        graph[u].append((v, w)) # 간선 연결
        graph[v].append((u, w))
        union(u, v)
        min_cost += w
        ct += 1
        if ct == N - 1: # 연결된 간선 수가 N - 1개면 MST 완성이므로 중지
            print(min_cost)
            break

_, far = dfs(0, -1) # 먼저 0번에서 가장 먼 노드를 찾고
print(dfs(far, -1)[0]) # 찾은 노드에서 가장 먼 노드까지의 거리가 트리의 지름이 된다.