[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)

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

20010번: 악덕 영주 혜유

 

 

[ 문제풀이 ]

 

1. node struct를 만들어서 arr 배열에 a, b, c를 각각 저장합니다.

 

2. c를 기준으로 arr배열을 오름차순으로 정렬합니다.

 

3. Union-Find를 이용하여 마을들을 연결하고, 열결이 될 때마다 ans에 c를 더해줍니다.

 

4. 또한, 연결이 될 때마다 연결이 된 교역로만으로 그래프를 다시 만듭니다.

 

5. 새로 만든 그래프를 이용하여 한 마을에서 가장 먼 마을을 구하고, 다시 그 마을로부터 가장 먼 마을까지의 거리를 따로 저장합니다.

 

6. ans와 가장 먼 마을까지의 거리를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, K;
node arr[1000000];
int vect[1000];
vector<pair<int,int>> list[1000];
int visited[1000];
int Max;
int start;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
void dfs(int n, int cost)
{
    if (cost > Max) {
        Max = cost;
        start = n;
    }
 
    for (auto& next : list[n]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, cost + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c);
    }
 
    sort(arr, arr + K, cmp);
 
    int ans = 0;
 
    for (int i = 0; i < K; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const int c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            list[a].push_back({ b,c });
            list[b].push_back({ a,c });
            Union(a, b);
            ans += c;
        }
    }
 
    visited[0] = 1;
    dfs(0, 0);
 
    Max = 0;
    fill(visited, visited + N, 0);
 
    visited[start] = 1;
    dfs(start, 0);
 
    printf("%d\n%d", ans, Max);
}