[Algorithm] 백준 1043 거짓말 - C++, Union Find

1043번: 거짓말

#include <iostream>
#include <vector>
using namespace std;

int n, m;  // number of people, partys
int truthCount;
int group[51];  // 2 : know truth, 1 : heard lie, 0 : first party
vector<int> partyList[51];
vector<int> truthList;

int FindGroup(int x){
    if(group[x] == x)
        return x;
    return group[x] = FindGroup(group[x]);
}

bool isSameGroup(int x, int y){
    x = FindGroup(x);
    y = FindGroup(y);

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

void Merge(int x, int y){
    x = FindGroup(x);
    y = FindGroup(y);

    group[x] = y;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 51; i++)
        group[i] = i;

    // input
    cin >> n >> m;
    cin >> truthCount;
    for(int i = 0; i < truthCount; i++){
        int input;  cin >> input;
        truthList.push_back(input);
    }

    // input party
    for(int party = 0; party < m; party++){
        int peopleCount;    cin >> peopleCount;

        for(int i = 0; i < peopleCount; i++){
            int people; cin >> people;

            partyList[party].push_back(people);
        }
    }

    // Union Group
    
    for(int i = 0; i < m; i++){
        int firstMan = partyList[i][0];
        for(int j = 1; j < partyList[i].size(); j++){
            int secondMan = partyList[i][j];
            Merge(firstMan, secondMan);
        }
    }

    // solve
    int answer = m;
    for(int i = 0; i < m; i++){
        bool isTruthParty = false;

        for(int j = 0; j < partyList[i].size(); j++){
            if(isTruthParty)
                break;

            int present = partyList[i][j];
            for(int k = 0; k < truthList.size(); k++){
                if(isSameGroup(present, truthList[k])){
                    isTruthParty = true;
                    break;
                }
            }
        }

        if(isTruthParty)    
            answer--;
    }

    // output
    cout << answer << '\n';
}

---

 풀이 방법을 처음에는 '매 탐색마다 group 비교를 하고 진실을 아는 사람이 없으면 answer++!' 로 했었다가 이후 보니깐 이전 파티에서 과장된 말을 들은 뒤 이후 진실을 아는 사람을 만날 가능성이 있는걸 놓쳤습니다.

 

 그래서 풀이 방법을 변경해 일단 입력을 전부 받은 뒤 각 파티에서 Union을 진행한 뒤 이후 파티들을 되돌아보면서 같은 그룹의 사람중 진실을 아는 사람들과 같은 그룹인지를 비교합니다. 여기서 그룹이 같다는 뜻은 건너건너라도 같은 소식을 들을 가능성이 있다는 이야기이므로 알고리즘을 풀 수 있게 됩니다.

 

 추가적으로 마지막 비교를 하는 for문은 조건을 통해서 break를 걸어주면 시간을 더 단축할 수 있게 됩니다.