[C++] 백준/BOJ - 20955 : 민서의 응급 수술

문제 이해 단계

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

20955번: 민서의 응급 수술

뉴런(노드) N개와 시냅스(간선) M개가 들어온다.
이후 M 줄에 걸쳐 연결된 두 뉴런의 정보가 들어온다.

만들어야 하는 것은 하나로 연결된 트리, 즉 사이클이 존재하지 않아야 한다.
만약 사이클이 존재한다면 그 사이클을 끊어야 한다.

이러한 조건일 때 모든 뉴런을 하나의 연결된 트리로 만들 때
필요한 최소 연산 횟수를 구하는 문제

 

---

문제 접근 단계

문제에서 대놓고 뉴런과 시냅스, 그리고 연결된 두 뉴런의 정보를 준다고 했다.

친절하게 사이클이 존재하지 않는 트리를 만들라고 했기 때문에,
그래프 탐색 문제임이 명확하다.

사이클이기 때문에 Union & Find를 이용해서 사이클이 발생하는지를 체크하겠다.

Union & Find 알고리즘 유명하기도 하고,
모른다면 코드에서 설명하는 것이 빠르기 때문에 코드로 설명하겠다.

특이한 점은 사이클이 발생했다면 사이클을 끊어야 한다는 점이다.

사이클이 발생하는지를 확인할 수는 있다.
그런데 사이클이 이미 발생했고 이를 끊는 것은 어떻게 하지?

그리고 입력으로 연결된 두 노드가 들어온다는 것도 특이한 것 같다.

---

입력받을 때부터 체크하기

사이클이 이미 발생했을 때
이걸 체크하는 방법을 생각할 필요가 없는 게,

사실 입력받을 때부터 사이클을 형성하는지 체크하면 된다.

이게 무슨 말이냐면,
음에는 없다고 생각하다가 입력을
하나씩 받으면서 노드를 연결한다고 생각하면
사이클이 발생하는 구간이 생길 것이다.

이때 사이클이 생기는 것을 방지할 수 있다.

---

이어져 있지 않은 노드 연결

사실 이건 굉장히 간단하다. 원리를 생각하면 된다.

우리가 만들어야 하는 건 하나로 연결된 트리이다.

즉, 연결이 하나도 되어있지 않는 것만 하나라도 연결하면 된다.

그리고 어차피 문제 조건에서
"두 뉴런 사이에 시냅스는 하나밖에 존재하지 않는다"라고 했기 때문에
아무것도 이어져있지 않는 노드 당 1개씩만 작업을 해주면 된다.

간단하게 말하면, 작업 횟수는 아무것도 이어져있지 않은 노드 당 1회이다.

---

사이클 발생한 노드 연결 끊기

다음은 사이클이 발생한 노드를 끊는 건 어떻게 할까에 대한 것이다.
이것도 마찬가지도 엄청 쉽다.

그냥 사이클이 발생한 간선 중 아무거나 하나 끊으면 되기 때문에,
사실상 사이클당 작업이 하나밖에 발생하지 않는다.
즉, 사이클 개수 당 1회이다.

최종적으로 이 문제의 답은 사이클의 개수 + 이어져있지 않은 노드이다.

바로 문제 구현 단계로 가보자.

 

---

문제 구현 단계

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

int parent[100001];
int ans = 0;
int N, M;

// 루트 부모 찾기(같은지 확인)
int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

// Union 집합 합치기
void merge(int x, int y){
    x = find(x);
    y = find(y);
    if(x > y) parent[x] = y;
    else parent[y] = x;
}

int main(){

    scanf("%d %d",&N,&M);
    for(int i = 0; i <= N; i++) parent[i] = i;
    int cycle = 0; // 싸이클 발생 갯수
    
    while(M--){
        int v1,v2;
        scanf("%d %d",&v1,&v2);
        // 싸이클 발생시 + 1
        if(find(v1) == find(v2)){
            cycle++;
            continue;
        }
        merge(v1,v2);
    }
    int ans = 0;
    for(int i = 1; i <= N; i++){
        if(parent[i] == i) ans++;
    }
    cout << ans+cycle-1; // -1을 해준 이유는 전체 덩어리도 포함됐기 때문
}

사실 아이디어가 어려운 문제였지, 코드는 어렵지 않다.

마지막에 -1을 해준 이유는 parent [i] = i에서
전체적인 덩어리도 포함됐기 때문에 1을 빼줘야 하기 때문이다.

 

---

시행착오

요즘 푸는 게 없어서 슬프다.

이것도 유니온 파인드까지는 했는데,
마지막 아이디어가 떠오르지 않았다.

저런 생각을 솔직히 어떻게 하지.. 난 죽어도 못할 거 같은데
자괴감 좀 그만 들고 싶은데

https://toss.me/howudong

howudong님에게 보내주세요