[백준/C++] 사이클 게임 (No. 20040)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 그냥 사이클이 존재하는지 확인하는 문제가 아니라 간선을 추가하면서 사이클이 존재하는지 확인하고, 만약 사이클이 존재한다면 몇 번째에서 사이클이 만들어졌는지 출력하는 문제다.

 

임의의 두 노드를 연결하는 간선이 추가될 때 마다 사이클이 만들어 지는지 확인하는 조건은 간단하다.

두 노드사이에 간선이 생기기 전에도 두 노드가 다른 노드를 통해 연결되었는지 확인하면 된다.

 

그림을 보면 이해가 쉽다.

 

위 그림과 같이 두 노드가 이미 연결된 상태에서 두 노드를 잇는 간선이 생기자 사이클이 완성되는 모습을 볼 수 있다.

 

이제 사이클이 만들어지는 조건을 알았기 때문에 두 노드가 연결된 상태인지 파악하는 방법을 구현하면 문제를 쉽게 풀 수 있다.

 

다양한 방법이 있겠지만, 두 노드가 연결되어 있다는 것은 같은 집합에 속해있다는 것과 같은 의미다.

 

그러므로 Union-Find 알고리즘을 이용해 두 노드가 같은 집합에 있는지 파악한다.

 

두 노드가 만약 같은 집합에 속해 있다면 (즉, 이미 연결된 상태라면) 간선이 추가될 경우 사이클을 만들게 된다.

 

만약 다른 집합에 속해있다면, 집합의 대표원소를 바꿔 같은 집합으로 변경해 문제를 풀면 된다.

 

 

​

[아이디어 정리]

1. 사이클이 만들어지는 조건은 간선을 추가했을 때,  이미 두 노드가 연결된 상태인 경우다.
2. 두 노드가 연결된 상태를 표시하기 위해 Union - Find 알고리즘을 이용한다.
3. 만약 두 노드 사이에 간선이 생겼을 때, 대표 원소가 같다면 그 때 횟수를 출력한다.
4. 만약 두 노드 사이에 간선이 생겼을 때, 대표 원소가 다르다면 두 집합을 합친다.

 

 

 

Code

 

 

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

int FindPar(vector<int> &par, int n)
{
    if (n == par[n]) {
        return n;
    }
    return FindPar(par, par[n]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N,M;
    cin >> N>>M;
    
    vector<int> par(N);
    for (int i = 0; i < N; i++)
        par[i] = i;
    int a, b, pa,pb,tmp;
    int answer = 0;
    for (int i = 1; i <= M; i++) {
        cin >> a >> b;
        pa = FindPar(par, a);
        pb = FindPar(par, b);
            
        if (pa==pb)
        {
            cout<< i;
            return 0;
        }
        else
        {
            tmp = min(pa, pb);
            par[pa] = tmp;
            par[pb] = tmp;
        }
    }
    cout << 0;
    return 0;
}

 

---

단계별로 풀기를 따라서 문제를 풀다보니 Union-Find 유형의 문제인 것을 알고 있었다.

만약 유형을 몰랐다면, 빠르게 풀 수 있었을지 의문이 든다.

단계별로 풀기 대신 골랜디를 시작해야 할 것 같은데...

 

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