[백준/C++] 1043번. 거짓말 유니온 파인드 풀이

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

1043번: 거짓말

 

0. 잡설

오랫동안 고민하던 문제를 풀게되어 글을 작성합니다.

유니온 파인드로 정답을 풀 수 있었습니다. 삽질한 기록까지 적어놓아 생각을 정리하려고 합니다.

 

1. 삽질

유니온 파인드 알고리즘을 연습하는 중이라 처음에 삽질이 있었습니다.

처음 생각해낸 아이디어는 다음과 같았습니다.

진실을 아는 사람은 parents배열 인덱스를 0으로 지정하고,
파티에서 진실을 아는 사람과 모르는 사람이 있는 경우, 진실을 알게된 사람의 parents배열 인덱스를 0으로 지정하자!

 

하지만 이렇게 하면, 순서에 따라 답이 다를 수 있었습니다.

예를 들어 다음과 같은 예제가 있겠습니다.

 

<입력>

5 4

1 5

2 1 2

2 2 3

2 3 4

2 4 5

 

잘못된 생각으로 적용된 알고리즘입니다.

순서에 따른 parents 배열 변화를 적어보겠습니다.

 

<초기화 parents 배열>

0 1 2 3 4 5

 

 

<진실을 아는 사람이 적용된 parents 배열>

0 1 2 3 4 0

 

<1,2 번 파티에서 변화한 parents 배열>

0 1 2 3 4 0

1, 2번 모두 진실을 모르므로 변화가 없습니다.

 

<2, 3번 파티에서 변화한 parents 배열>

0 1 2 3 4 0

2, 3번 모두 진실을 모르므로 변화가 없습니다.

 

<3, 4번 파티에서 변화한 parents 배열>

0 1 2 3 4 0

3, 4번 모두 진실을 모르므로 변화가 없습니다.

 

<4, 5번 파티에서 변화한 parents 배열>

0 1 2 3 0 0

5번사람이 진실을 알고 있으므로, 4번도 진실을 알게 되었습니다. 

 

이제, 진실을 알고 있는 사람인 4번과 5번이 0이 되었으므로 다시 파티를 점검해 거짓말을 할 수 있는 파티의 갯수를 세줍시다. 

(잘못된 생각입니다!!)

파티 인덱스	참여한 사람	거짓말을 할 수 있는지?
0	1, 2	O
1	2, 3	O
2	3, 4	X
3	4, 5	X

이렇게 되면 잘못된 정답인 2를 출력하게 됩니다. 정답은 0이 되어야 합니다.

3번 사람은 4번에게 진실을 전달받고, 2번 사람은 3번에게 진실을 전달받고, 1번 사람은 2번에게 진실을 전달받아야 하는데, 단순하게 4, 5번만 0처리를 했으므로 진실에 대한 전파가 되지 않습니다.

 

2. 유니온 파인드 풀이

파티에서 진실을 전파하고, 다시 파티를 점검한다는 큰 아이디어는 같습니다.

하지만 유니온 파인드에서는 각각의 부모 노드를 연결해준다는 점이 다릅니다.

 

부모를 유니온 하는 부분까지 코드는 다음과 같습니다.

//
//  거짓말.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2022/03/02.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m;
vector<int> parties[55];
int parents[55];


int find_parent(int x){
    if(parents[x] == x) return x;
    
    return parents[x] = find_parent(parents[x]);
}

void union_parents(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    
    if(a<b) parents[b] = a;
    else parents[a] = b;
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    
    for(int i=1; i<=n; i++) parents[i] = i;
        
    //진실을 아는 사람들의 부모를 0으로 초기화해줍니다.
    int t;
    cin>>t;
    for(int i=0; i<t; i++){
        int know_truth;
        cin>>know_truth;
        parents[know_truth] = 0;
    }
    
    //우선 파티 리스트를 받습니다. 부모를 계속 Union합니다.
    for(int i=0; i<m; i++){
        int party_mans;
        cin>>party_mans;
        
        int temp;
        int prev;
        cin>>temp;
        
        prev = temp;
        parties[i].push_back(temp);
        
        for(int j=1; j<party_mans; j++){
            int idx;
            cin>>idx;
            
            union_parents(prev, idx);
            prev = idx;
        }
    }

파티의 인원을 입력받을 때 전에 입력된 사람과 계속 유니온을 진행해줍니다. 같은 파티에 참가한 사람 중 진실을 아는 사람이 있다면 최 상단에 0의 값을 가지는 부모를 가지게 됩니다.

 

이제 다시 파티를 검사하여 정답을 찾아줍니다. 어떤 파티의 참석 인원 중에 최상단 부모가 0이라면, 이 파티에서는 진실을 말할 수 없습니다.

//파티 리스트를 검사합니다.
    int ans = 0;
    for(int i=0; i<m; i++){
        int is_can_tell_lie = 1;
        for(int j=0; j<parties[i].size(); j++){
            if(find_parent(parents[parties[i][j]]) == 0){
                is_can_tell_lie = 0;
                break;
            }
        }
        
        if(is_can_tell_lie) ans++;
    }
    
    cout<<ans;
    
    return 0;
}

3. 유니온 파인드 예외 점검

잘못된 풀이에서 들은 예외를 다시 유니온 파인드에서 적용해봅시다.

<입력>

5 4

1 5

2 1 2

2 2 3

2 3 4

2 4 5

 

순서에 따른 parents 배열 변화를 적어보겠습니다.

 

<초기화 parents 배열>

0 1 2 3 4 5

 

<진실을 아는 사람이 적용된 parents 배열>

0 1 2 3 4 0

 

<1,2 번 파티에서 변화한 parents 배열>

0 1 1 3 4 0

2번 사람의 부모가 1번과 통합되었습니다.

 

<2, 3번 파티에서 변화한 parents 배열>

0 1 1 1 4 0

3번 사람의 부모가 2번 사람과 통합되었습니다.

 

<3, 4번 파티에서 변화한 parents 배열>

0 1 1 1 1 0

4번 사람의 부모가 3번사람과  통합되었습니다.

 

<4, 5번 파티에서 변화한 parents 배열>

0 0 1 1 1 0

4번의 최상단 부모가 1번인데, 5번으로 인해 내용이 1번의 내용 0으로 바뀌었습니다.

결국, 1번이 진실을 알게 되었으므로 1번에 연결된 2, 3, 4번이 모두 진실을 알게 되었습니다.

 

이제, 진실을 알고 있는 사람인 4번과 5번이 0이 되었으므로 다시 파티를 점검해 거짓말을 할 수 있는 파티의 갯수를 세줍시다. 

파티 인덱스	참여한 사람	최상단 부모(그룹)	거짓말을 할 수 있는지?
0	1, 2	1	X
1	2, 3	1	X
2	3, 4	1	X
3	4, 5	1	X

 

4. 최종 정답 코드

//
//  거짓말.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2022/03/02.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m;
vector<int> parties[55];
int parents[55];


int find_parent(int x){
    if(parents[x] == x) return x;
    
    return parents[x] = find_parent(parents[x]);
}

void union_parents(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    
    if(a<b) parents[b] = a;
    else parents[a] = b;
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    
    for(int i=1; i<=n; i++) parents[i] = i;
        
    //진실을 아는 사람들의 부모를 0으로 초기화해줍니다.
    int t;
    cin>>t;
    for(int i=0; i<t; i++){
        int know_truth;
        cin>>know_truth;
        parents[know_truth] = 0;
    }
    
    //우선 파티 리스트를 받습니다. 부모를 계속 Union합니다.
    for(int i=0; i<m; i++){
        int party_mans;
        cin>>party_mans;
        
        int temp;
        int prev;
        cin>>temp;
        
        prev = temp;
        parties[i].push_back(temp);
        
        for(int j=1; j<party_mans; j++){
            int idx;
            cin>>idx;
            
            union_parents(prev, idx);
            prev = idx;
        }
        cout<<"\n";
        for(int i=0; i<=n; i++)cout<<parents[i]<<" ";
    }
    
    //파티 리스트를 검사합니다.
    int ans = 0;
    for(int i=0; i<m; i++){
        int is_can_tell_lie = 1;
        for(int j=0; j<parties[i].size(); j++){
            if(find_parent(parents[parties[i][j]]) == 0){
                is_can_tell_lie = 0;
                break;
            }
        }
        
        if(is_can_tell_lie) ans++;
    }
    
    cout<<ans;
    
    return 0;
}