[백준] 20955번 민서의 응급 수술 (C++)

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

 

 

이 문제는 뉴런이라는 트리가 입력으로 주어질때 

1. 뉴런끼리 연결하는 간선을 추가

2. 뉴런끼리 연결하는 간선을 제거

 

두 가지 행동을 최소로 사용해 하나의 뉴런으로 만드는 횟수를 출력하는 문제이다.

 

 

위 그림처럼 간선을 추가하는 경우는 하나의 트리가 아닌 여러개의 트리가 존재할때

그 트리들을 하나로 연결하기 위해서는 트리의 개수 -1 개의 간선 추가가 필요하다.

 

하지만 간선을 제거하는 경우는 사이클이 존재하는 트리가 주어질 때 

사이클을 제거하기 위해서 간선을 제거해야한다.

 

즉 점화식은 트리의 개수 + 사이클 개수 - 1이 된다.

 

따라서 유니온 파인드(분리 집합)을 사용하여 입력으로 들어오는 간선을 비교하여 같은 노드에 있는지 확인하며

만약 같은 노드에 있는 경우는 사이클이 존재한다는 것이므로 사이클 개수를 추가해준다.

 

이후 set에 부모 노드를 넣어줌으로써 트리의 개수를 알 수 있기 때문에

set의 크기 + 사이클 개수 - 1을 해주었다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M;
int unf[100001];
set<int> st;
int cycle;

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a > b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b) return true;
    else return false;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

void solve() {
    for(int i = 1; i <= N; i++) {
        st.insert(Find(i));
    }

    cout << cycle + st.size()-1;
}

void input() {
    cin >> N >> M;

    Init();

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        if(!isUnion(a, b)) {
            Union(a, b);
        }
        else {
            cycle++;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

처음에 문제를 보고 트리인 것을 보고 무조건 dfs를 사용해야 할것 같았다. 그래서 dfs를 사용하여

사이클이 존재하는지 유무를 판별하고 개수를 증가시키고 트리의 개수를 세주었는데

중간에 계속 틀려서 질문 게시판을 보고 몇개의 반례에서 통과하지 못하는 것을 알았다...

 

결국 분류를 보니 유니온 파인드로 풀 수 있는것을 보고 바로 풀었는데 이런점에서 약간 부족한것 같다

강한 확신이 오히려 독이 된다는 느낌이다..