군사 이동

백준 11085번: 군사 이동

아이디어

C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다.
간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답!

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct _data {
    int s, e, w;

    bool operator<(_data d) {
        return w > d.w;
    }
} Data;

int P, W, C, V;
int p[1000];

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

void Union(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    p[n1] += p[n2];
    p[n2] = n1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> P >> W;
    cin >> C >> V;
    vector<Data> v;

    for (int i = 0; i < W; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v.push_back({s, e, w});
    }
    memset(p, -1, sizeof(p));
    sort(v.begin(), v.end());
    for (auto d : v) {
        Union(d.s, d.e);
        if (find(C) == find(V)) {
            cout << d.w;
            break;
        }
    }
    return 0;
}

여담

문제 뭔소린지 이해 안돼서 한참 읽었다. 난 붕어다.