[ 백준 ] 11085번 - 군사 이동 (C++)

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

11085번: 군사 이동

 

 

[ 문제풀이 ]

 

1. vect[ p ] 배열을 만들어 각 지점의 부모 노드를 저장합니다.

 

2. Union-Find를 이용하여 각 지점을 잇고, 이은 길 중 가장 좁은 길을 ans에 저장합니다.

 

3. 지점을 이을 때마다 두 수도가 이어져 있는지 체크하고, 이어져 있다면 ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int start;
    int end;
    int width;
};
 
bool cmp(node left, node right) {
    return left.width > right.width;
}
 
int p, w, c, v;
node arr[50000];
int vect[1000];
 
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;
}
 
int main()
{
    scanf("%d %d %d %d", &p, &w, &c, &v);
 
    for (int i = 1; i < p; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < w; i++) {
        int s, e, w;
        scanf("%d %d %d", &s, &e, &w);
        arr[i] = { s,e,w };
    }
 
    sort(arr, arr + w, cmp);
 
    int ans = 1000;
 
    for (int i = 0; i < w; i++) {
        const int a = arr[i].start;
        const int b = arr[i].end;
        const int width = arr[i].width;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans = min(ans, width);
 
            if (Find(c) == Find(v)) {
                printf("%d", ans);
                return 0;
            }
        }
    }
}