[c++] BOJ 20040 :: 사이클 게임

문제

[사이클 게임 문제 바로가기]

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

 

풀이

결국 사이클인지를 탐색하는 방법의 시간복잡도가 중요하다. m번의 차례는 어차피 살펴보아야 하니 1,000,000(10^6) 시간복잡도의 반복문을 돌게 되는데 시간복잡도가 나지 않기 위해서는 내부에 10^3 이상의 시간복잡도를 가진 알고리즘이 있으면 안된다.내부에서는 사이클이 존재하는 지를 판단해야하는데 그 방법은 다음 3가지가 있다. (노드의 총 개수를 n이라고 하자.)

1. dfs로 판단 : edge가 추가될 때마다 node를 dfs하여 같은 node가 나오는 지 체크한다. 시간복잡도는 O(n)이다.
2. 집합으로 판단 : edge가 추가될 때마다 이어진 node들을 같은 집합에 넣는다(굳이 넣을 필요없이 같은 집합이라고 표시한다). 이 때, 이미 node가 해당 집합에 있는 지 체크한다. 시간복잡도는 O(n)이다.
3. union-find : 부모 node를 저장해두었다가 새로 추가된 edge의 두 node가 같은 parent를 가지고 있는지 체크한다. 시간복잡도는 O(lgn)이다.

 

따라서 3번째 방법인 union-find를 적용해야 n의 범위인 500,000(10^5)를 감당할 수 있다.

 

코드

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

vector<int> parentList;

int parent(int idx){
	if(parentList[idx] == idx){
		return idx;
	}
	return parentList[idx] = parent(parentList[idx]);
}

bool unionGroup(int c, int p){
	int parentC = parent(c);
	int parentP = parent(p);
	if(parentC == parentP){
		// 사이클
		return false;
	}
	parentList[parentC] = parentP;
	return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
	int N, M; cin >> N >> M;
	
	for(int i=0; i<N; i++){
		parentList.push_back(i);
	}
	
	int res = 0;
	for(int i=0; i<M; i++){
		int c,p; cin >> c >> p;
		if(!unionGroup(c, p)){
			res = i+1;
			break;
		}
	}
	cout << res;
}

 

결과