[백준,c++] 20955번 - 민서의 응급 수술

문제

20955번: 민서의 응급 수술

 

코드

#include <iostream>
#define MAX 100001
using namespace std;

int N, M, ans;
int parent[MAX];

int find_parent(int a){
    if(a == parent[a]) return a;
    return parent[a] = find_parent(parent[a]);
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>M;
    
    for(int i=0; i<MAX; i++) parent[i] = i;
    
    for(int i=0; i<M; i++){
        int a, b; cin>>a>>b;
        if(find_parent(a) != find_parent(b)){
            make_parent(a,b);
        }
        else ans++; // 부모가 같은 경우(사이클이 생김) - 떼어내야 한다.
    }
    
    for(int i=1; i<=N; i++){  // 부모가 자기 자신인 경우 - 하나로 합쳐야 한다.
        if(i == find_parent(i)) ans++;
    }
    
    
    cout<<ans-1; // 바로 위에서 루트 노드도 합친경우를 빼준다.
}

 

풀이

유니온 파인드로 풀이가 가능한 문제였습니다. 

• 초기에 모든 노드의 부모는 자기 자신으로 세팅합니다.
• 입력을 받을 때 두 노드가 같은 부모가 아니라면 유니온 파인드를 통해 부모를 합쳐주고, 부모가 같다면 떼어내야 하기 때문에 횟수를 증가해줍니다.
• 그 후, 부모가 자기 자신인 경우 하나의 트리로 합쳐야 하는 이동 과정이 필요하기에 횟수를 증가합니다.

5 4
1 2
1 3
2 3
4 5

 

위 입력을 풀이하면 아래와 같습니다.

현재 parent[1] = 1, parent[2] = 2 이므로 부모가 다르기 때문에 합치는 과정을 통해 parent[1]= 1, parent[2] = 1로 만들어줍니다.

다음으로 parent[1] = 1, parent[3] = 3, 역시 부모가 다르기 때문에 합치는 과정을 통해 parent[1] = 1, parent[3] = 1로 만들어줍니다.

다음으로 parent[2] = 1, parent[3] = 1 이므로 둘 다 부모가 같으니 사이클이 생깁니다. 따라서 떼어내는 작업을 수행해야 하므로 횟수를 1 증가시켜줍니다.

parent[4] = 4, parent[5] = 5, 둘 다 부모가 다르기 때문에 합치는 과정을 통해 parent[4] = 4, parent[5] = 5로 만들어줍니다.

 

이제 입력이 전부 끝나면 트리를 하나로 합쳐주는 과정이 필요합니다.

현재 위 상황에서 node4를 node1 의 노드 쪽으로 붙여주면 하나의 노드가 되게 됩니다. 따라서 node = parent[node]인 경우는 전부 붙여준다고 생각하고 횟수를 증가시켜 주면 됩니다.

 

아래는 추가적인 테스트 케이스입니다.

3 2
1 2 
2 3

-> 0

8 7
1 3
1 2
2 4
3 4
5 6
5 7
6 7

-> 4

5 6
1 2 
1 3
1 4
2 5
3 5
4 5

->2