[C/C++] 백준 20040: 사이클 게임 (Union-Find)

20040: 사이클 게임

 

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

20040번: 사이클 게임

 

해설!

 이 문제는 최소 스패닝 트리를 구하기 위해서 필요한 연산인 Union-Find를 이용하면 쉽게 풀리는 문제였다. 이 문제를 Map이나 c++ 내부에 있는 자료구조를 이용하여 풀 경우에는 사실상 해결이 불가능한데 그 이유는 점의 개수가 최대 500,000개이며 진행되는 연산이 최대 1,000,000이기 때문이다. 그렇기 때문에 Union-find를 이용하여 그 연산시간이 O(logn) 이하로 만들어야지만 제한된 시간 내에 해결이 가능하다.

 Union-Find와 관련된 내용은 아래 포스팅의 상호배타적 집합 최적화 부분을 참고하면 된다!

 

https://donggul-godsang.tistory.com/90

[C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘)

  

 결국 하나의 집합(set)로 이루어져있다는 것을 tree를 만들어 유지하고 계산하겠다는 것인데 이런 식으로 구현한다면 연산시간을 매우 효과적으로 줄일 수 있다. 이런 개념을 사용한다는 점에서 DisjointSet은 위 포스팅과 이 문제의 코드가 똑같다.

 

 다만 달라진 점은 main 함수에서 입력 받은 두 수가 하나의 집합에 있다고 나온다면 현재 연산 차례를 출력하고 return 한다. 즉 구조체 DisjointSet의 내부 함수 find 연산을 이용한건데 입력 받은 두 수의 최상위 노드, 즉 루트가 같을 경우 이 두 수는 하나의 set안에 존재하는 것이기 때문에 이 두수를 받는 순간 cycle이 생기게 된다. 

 

 만약 이 두 수가 같은 set에 없다면 merge를 이용해 합쳐주는데 이때 중요한 점은 rank[] 배열을 이용하여 tree의 높이를 정해주는 것이다. tree가 한쪽으로 쏠리지 않게 최대한 균형을 잡도록 merge를 이용할 때 height가 작은 트리가 height가 큰 트리 밑으로 들어가 균형을 잡아준다.

 이 개념을 이용하면 쉽게 문제 해결이 가능하다!

 

 

소스코드!!

 

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

struct DisjointSet{
  vector<int> parent,rank; //항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어 넣어 높이가 높아지는 것을 방지=> O(n)이 되는 경우를 방지!!
  DisjointSet(int n):parent(n+1),rank(n+1,1){ //처음 초기화 해준건가??
    for(int i=0;i<=n;i++)
      parent[i]=i;
  }

  int find(int u) { //현재 트리에서 부모노드(root)를 찾는 과정
    if(u==parent[u]) //root는 자기 자신을 가르키고 있음
      return u;
    return parent[u]=find(parent[u]);
  }

  void merge(int u,int v){
    u=find(u),v=find(v); //각 노드의 부모를 찾음
    if(u==v) return; //이미 u와 v가 같은 트리에 속하는 경우 merge 하지 않음
    if(rank[u]>rank[v]) //u가 더 heigh가 낮게 되어 v와 합쳐졌을 때 검색에 시간이 오래 걸리지 않도록
      swap(u,v);   
    parent[u]=v; //한쪽의 노드가 다른쪽 노드의 자식이 됨!! => 하나의 트리로 들어가게 됨
    if(rank[u]==rank[v]) ++rank[v]; //두 트리의 높이가 같을 때에는 두 트리의 높이를 1늘려줘야함
    //나머지 경우에는 v의 높이에 맞게 저장됨
  }
};

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m;
  DisjointSet sets(n+1);
  int i=1;
  for(i=1;i<=m;i++){
    int tmp1,tmp2;
    cin>>tmp1>>tmp2;
    if(sets.find(tmp1)==sets.find(tmp2)){
      cout<<i;
      return 0;
    }
    sets.merge(tmp1,tmp2);
  }
  cout<<0;
  
}