[백준/Baekjoon] 1043 거짓말 C++ :: Union find

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

1043번: 거짓말

---

1. Logic

이 문제는 유니온파인드 알고리즘으로 풀 수 있다. 그 이유는 한명이 거짓말을 듣게 되면 다른 사람도 거짓말을 알기 때문에 알고있는 사람 모두 노드로 연결하여 처리해 주는 것이다.

그리고 나중에 연결된 노드들에서 진실을 알고있는 사람이 있다면 제외해주면 된다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

int node[51];
vector<vector<int>> party(51);
vector<int> know;

int find(int x) {
    if(node[x] == x) return x;

    return node[x] = find(node[x]);
}

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);

    if(x == y) return;
    
    if(x < y) node[y] = x;
    else node[x] = y;
}

bool isUnion(int a, int b) {
    int x = find(a);
    int y = find(b);

    if(x == y) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;

    for(int i = 0; i < k; i++) {
        int knowP;
        cin >> knowP;
        know.push_back(knowP);
    }

    for(int i = 1; i <= n; i++) node[i] = i;

    for(int i = 0; i < m; i++) {
        int cur;
        cin >> cur;
        int prev;
        cin >> prev;
        party[i].push_back(prev);
        for(int j = 1; j < cur; j++) {
            int after;
            cin >> after;

            merge(prev, after);
            prev = after;
            party[i].push_back(after);
        }
    }
    for(int i = 0; i < party.size(); i++) {
        bool check = false;
        for(int j = 0; j < party[i].size(); j++) {
            if(check) break;
            for(int k = 0; k < know.size(); k++) {
                if(isUnion(party[i][j], know[k])) {
                    check = true;
                    break;
                }
            }
        }
        if(check) m--;
    }
    cout << m;
}

---

3. Feedback

유니온파인드 문제를 오랜만에 풀어봐서 많이 까먹은 것 같다. 블로그에 유니온파인드에 대해서 정리해야겠다

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90