[백준 20040 C++][G4] 사이클 게임

⭐️ 난이도

 

Gold 4

---

⭐️ 문제

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

20040번: 사이클 게임

 

 

---

⭐️ Idea flow

 

문제를 요약하자면 다음과 같다.

1. 간선의 정보인 노드의 번호 두 개가 m번 주어진다.

2. 게임을 진행하다가(간선을 추가하다가) 

3. 싸이클이 완성되면 몇 번째 차례에서 완성이 되었는지 return

 

다른 그래프 문제들과는 다르게 간선을 미리 연결시켜놓고 문제를 푸는 것이 아니라,

간선을 연결시키면서 사이클이 완성되었는지의 여부를 확인해야하는 문제였다.

 

문제 구상 시기에는 DFS/BFS를 통해 사이클 형성 여부를 확인하려 했으나, 그렇게 하면 시간이 부족할 것 같았다.

그 다음으로 생각한 것이 분리 집합(Disjoint-set)이다.

parent 배열을 통해 특정 노드들이 연결되어 있는지의 여부를 확인할 수 있으므로, 만일 어떤 두 정점(노드)를 연결할 때에 

두 정점의 parent 값이 같다면 사이클이 형성된다는 뜻이다.

따라서 해당 조건에서 몇 번째 입력인지 출력하면 된다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 20040 - 사이클 게임
int n, m; // 점의 개수, 진행된 차례의 수
int result = 0;
vector<int> parent;


int getParent(int x){
    if(parent[x] == x)  return x;
    return parent[x] = getParent(parent[x]);
}

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

void initParent(){
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
}

void solve(){
    for(int i = 0; i < m; i++){
        int s, e;
        cin >> s >> e;
        s = getParent(s);
        e = getParent(e);
        
        if(s == e){ // 부모가 같다는 뜻은 이미 이어진 그래프라는 뜻
            result = i + 1;
            return;
        }
        unionParent(s, e);
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    parent.assign(n + 1, 0);
    initParent();
    solve();

    cout << result;

    return 0;
}

 

---

⭐️ Feedback

 

그래프 문제라고 하면 대부분 입력을 받으면서 간선을 모두 연결시켜놓고 그 이후에 처리를 하는 방식이었다.

이번 문제를 통해서 간선을 연결하면서 조건을 확인하는 문제가 있음을 알 수 있었고,

또한 그런 문제라면 DFS/BFS보다는 분리 집합이 시간적/공간적으로 더 유리함을 알 수 있었다.