BOJ 1717 : 집합의 표현

풀이 요약

유니온 파인드

풀이 상세

1. 유니온 파인드를 활용하는 문제로, 0 인 경우에는 대표값을 통일시키고 union , 1 인 경우에는 두 수의 대표값이 동일한지 확인하여 알맞은 출력한다. 나의 경우 $X,Y$ 의 대표값이 다른 경우 $X$ 의 대표값을 기준으로 통일하였다.

2. 유니온 파인드에 대한 이론지식이 충분하다면 큰 문제 없이 풀릴 거다.

배운점

• 맞왜틀을 시도했던 문제이다. p[x] == p[y] 와 p[findSet(x)] == p[findSet(y)] 다를 수 있다는 점을 확인했다.

코드

#include <iostream>
using namespace std;
const int N_MAX = 1e6 + 4;
int N, M;
int p[N_MAX], n1, n2, n3;

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

void output(string ans) { 
		cout << ans << "\n";
}

void unionParent(int x, int y, bool b) {
    int fx = findSet(x);
    int fy = findSet(y);

    if (fx == fy && b) output("YES");
    else if (fx != fy && b) output("NO");
    else p[fy] = fx
}

void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) p[i] = i;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    for (int i = 0; i < M; i++) {
        cin >> n1 >> n2 >> n3;
        unionParent(n2, n3, n1);
    }
    return 0;
}