[BOJ/Gold 3] 백준 25587 배수로(C++)

문제 링크

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

 

 

문제

ChAOS 나라에는 총 N개의 도시가 있고 각각 1, 2, 3, …, N번 도시라고 부른다. ChAOS 나라에 각 도시에는 홍수를 막기 위해 배수로가 설치되어 있다. i번 도시의 배수로는 강수량이 Ai 이하일 때만 홍수를 막을 수 있다. 추가로 한 도시에만 폭우가 올 때를 대비해, 두 개의 도시를 정해서 양쪽 도시의 배수로 용량을 공유할 수 있는 공사를 하기로 했다. 예를 들어 1번 도시와 2번 도시에 공사를 하고 난 후, 1번 도시와 2번 도시의 강수량의 합이 A1 + A2이하라면 1, 2번 도시 모두에 홍수가 나는 것을 막을 수 있고, 그렇지 않다면 1, 2번 도시 모두에 홍수가 나게 된다. 그 후 2, 3번 도시에도 공사를 하면, 세 도시의 강수량의 합이 A1 + A2 + A3이하라면 1, 2, 3번 도시 모두에 홍수가 나는 것을 막을 수 있고, 그렇지 않다면 1, 2, 3번 도시 모두에 홍수가 나게 된다.

그리고 현재 ChAOS 나라에는 전국적으로 폭우가 오고 있다. 현재 i번 도시의 강수량은 Bi다. 여기서 두 가지의 쿼리를 처리하는 프로그램을 작성하자.

•  1 x y : x번 도시와 y번 도시에 공사를 한다.
•  2 : 현재 상태에서 홍수가 날 도시의 개수를 출력한다.

단, 2번 쿼리는 최소 한 개 주어진다.

입력

첫 번째 줄에 도시의 개수인 정수 N(3 ≤ N ≤ 100,000)과 쿼리의 개수인 정수 M(1 ≤ M ≤ 100,000)이 주어진다.

두 번째 줄에는 i번 도시의 배수로 용량을 의미하는 N개의 정수 A1, A2, A3, ..., AN이 주어진다. (0 ≤ A​i ≤ 1,000)

세 번째 줄에는 i번 도시의 강수량을 의미하는 N개의 정수 B1, B2, B3,  ..., BN이 주어진다. (0 ≤ Bi ≤ 1,000)

네 번째 줄부터 M + 3번째 줄까지는 1 x y 또는 2 형태의 쿼리 M개가 한 줄에 하나씩 주어진다. (1 ≤ x, y ≤ N)

출력

각각의 2번 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

2
1

예제 입력 2

5 6
1 1 1 1 1
5 0 0 0 0
1 1 2
1 2 4
2
1 3 5
1 3 4
2

예제 출력 2

3
0

알고리즘 분류

• 유니온 파인드

풀이

최대 100,000개의 파이프의 Parent를 일일히 찾아서 배수로 용량과 강수량을 비교하는 작업을 반복하기엔 시간이 부족하다.

따라서 2번 명령을 O(1)의 시간 안에 수행하고 싶다.

그렇게 하려면 홍수가 날 도시의 개수에 대한 정보를 Answer 변수에 미리 저장해두는 것이 좋아보인다.

처음에 입력받은 배수로 용량과 강수량을 비교하면서 강수량이 배수로 용량보다 더 큰 도시들만을 센다.

그리고 M번의 쿼리를 수행하면서 1번 명령을 수행해야 한다면 X 도시와 Y 도시를 묶어주면서 홍수가 날 도시의 개수를 판단한다.

우선 각각의 도시의 Parent인 PX, PY에 속해 있는 집합의 배수로 용량이 강수량보다 적다면 해당 도시의 정보, 즉 해당 도시와 같은 집합에 속해 있는 모든 도시들 중 홍수가 날 도시의 개수만큼을 Answer 변수에 저장된 값에서 제외한다.

그리고 PX, PY를 비교해 더 작은 값을 더 큰 값의 Parent로 정하고, Child의 배수로 용량, 강수량, 홍수가 날 도시의 개수를 Parent의 정보에 더해준다.

마지막으로 Parent의 배수로 용량이 강수량보다 적다면 Answer에 다시 홍수가 날 도시의 개수만큼을 더해준다.

이렇게 되면 집합을 union할 때마다 홍수가 날 도시를 중복으로 세지 않게 되면서 그 개수를 구할 수 있게 되어 2번 명령을 O(1)만에 수행할 수 있게 된다.

코드

#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;
int N, M, I, X, Y;
int A[MAX], B[MAX], Parent[MAX], Count[MAX];

int Answer;

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

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

void union_group() {
    int PX = find(X);
    int PY = find(Y);
    if (PX != PY) {
        if (PX > PY) {
            swap(PX, PY);
        }
        if (A[PX] < B[PX]) {
            Answer -= Count[PX];
        }
        if (A[PY] < B[PY]) {
            Answer -= Count[PY];
        }

        Parent[PY] = PX;
        A[PX] += A[PY];
        B[PX] += B[PY];
        Count[PX] += Count[PY];

        if (A[PX] < B[PX]) {
            Answer += Count[PX];
        }
    }
}

void settings() {
    union_group();
}

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

void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
        if (A[i] < B[i]) {
            Answer++;
        }
        Count[i] = 1;
    }
    while (M--) {
        cin >> I;
        if (I == 1) {
            cin >> X >> Y;
            settings();
        }
        else {
            find_Answer();
        }
    };
}

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

    return 0;
}