[BOJ/Gold 3] 백준 27945 슬슬 가지를 먹지 않으면 죽는다(C++)

문제 링크

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

 

문제

키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다.

각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 ti일에만 문을 여는 가지 디저트 노점이 있다. (ti는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다. 심지어 기억력도 퇴화해 N - 1개의 길만을 기억할 수 있게 되었다!

모든 요리 학원에 다닐 수 있도록 N-1개의 길을 골랐을 때, 키위새가 쓰러지는 날이 d일차라고 하자. 날짜가 1일차부터 시작할 때, d의 최댓값을 구해보자.

입력

첫째 줄에 요리 학원의 수 N, 길의 수 M이 주어진다. (2 ≤ N ≤ 10^5; N - 1 ≤ min(5 × 10^5, (N 2))

둘째 줄부터 M개 줄에 각 길이 연결하는 두 학원의 번호 ui, vi, 길에 있는 노점이 여는 날 ti가 주어진다. (1 ≤ ui, vi ≤ N; ui ≠ vi; 1 ≤ ti ≤ 10^9; ti ≠ tj)

각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다.

두 요리 학원 사이를 곧바로 잇는 길은 많아야 하나이다.

출력

첫째 줄에 d의 최댓값을 출력한다.

예제 입력 1

4 5
1 3 1
3 2 3
4 1 2
4 2 4
2 1 5

예제 출력 1

4

예제 입력 2

10 15
1 2 18
1 5 19
1 6 15
2 3 12
2 4 9
3 8 11
3 10 6
4 7 7
4 9 4
5 9 14
5 10 8
6 7 3
6 8 17
7 10 16
8 9 10

예제 출력 2

1

어떤 길을 골라도 1일차에 노점을 방문할 수 없다.

알고리즘 분류

• 유니온 파인드

풀이

M개의 양방향 길의 정보를 입력받고 T를 기준으로 오름차순한다.

그리고 양방향 길을 차례대로 탐색하면서 먼저 현재 길의 T와 D가 일치하는 지, 즉 현재 길의 노점이 1일차에 문을 여는지를 파악하고, 1일차에 문을 연다면 두 요리 학원을 같은 집합으로 만들고 D를 증가시킨다. 그리고 다음 길이 2일차에 문을 여는지 확인하고 문을 연다면 다시 두 요리 학원을 같은 집합으로 만든다.

M개의 길이 노점을 여는 날짜는 전부 다르므로 최대 M번의 길을 탐색할 수 있으며, 만약에 현재 길의 노점을 여는 날짜가 D와 다르다면 탐색을 종료하고 D를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct INFO {
    int U, V, T;
};

int N, M;
vector<INFO> Edge;
int Parent[MAX];
int D = 1;

void init() {
    for (int i = 0; i < MAX; i++) {
        Parent[i] = i;
    }
}

void input() {
    cin >> N >> M;
    Edge.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> Edge[i].U >> Edge[i].V >> Edge[i].T;
    }
}

int find_Parent(int X) {
    if (Parent[X] == X) {
        return X;
    }
    return Parent[X] = find_Parent(Parent[X]);
}

void union_Group(int X, int Y) {
    int PX = find_Parent(X);
    int PY = find_Parent(Y);
    if (PX < PY) {
        Parent[PY] = PX;
    }
    else {
        Parent[PX] = PY;
    }
}

bool Comp(INFO A, INFO B) {
    return (A.T < B.T);
}

void settings() {
    sort(Edge.begin(), Edge.end(), Comp);
    for (int i = 0; i < M; i++) {
        int U = Edge[i].U;
        int V = Edge[i].V;
        int T = Edge[i].T;
        if (T != D) {
            break;
        }
        if (find_Parent(U) != find_Parent(V)) {
            union_Group(U, V);
            D++;
        }
    }
}

void find_Answer() {
    cout << D << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}