BOJ 17250 : 은하철도

문제링크

풀이요약

유니온 파인드

풀이상세

1. 현재 연결된 은하간의 총 행성의 수를 묻는 문제이다.

2. 부모 배열을 활용한 대표값 찾기를 통해 해결하였으며, 매 연결동안의 행성간의 합을 저장하기 위한 용도로 sum 배열을 만들었다. 초기 sum 배열에는 기존 은하마다 가지고 있는 값들이 들어가며, 은하간 연결 시, 대표값에 자신이 현재 가진 행성의 수를 더한다.

3. 해당 풀이의 경우 작은 부모 기준으로 부모를 통일시켰다.

#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<int> a, p, sum;

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    a.push_back(0), p.push_back(0), sum.push_back(0);
    int num;
    for (int i = 1; i <= N; i++) {
        cin >> num;
        a.push_back(num);
        p.push_back(i);
        sum.push_back(a[i]);
    }
}

int getParent(int n) {
    if (p[n] == n) return n;
    return p[n] = getParent(p[n]);
}

int unionParent(int pa, int pb) {
    if (pa < pb) {
        sum[pa] += sum[pb];
        p[pb] = pa;
        return sum[pa];
    } else if (pa > pb) {
        sum[pb] += sum[pa];
        p[pa] = pb;
        return sum[pb];
    }
    return sum[pa];
}

void go() {
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        cout << unionParent(getParent(a), getParent(b)) << "\n";
    }
}

int main() {
    input();
    go();
}