[BOJ] 백준 20040. 사이클 게임 (Gold IV)

심심해서 학교 제출현황, 그리고 울학교 랭커분들 제출현황 둘러보다가 발견한 재밌는 문제이다. 실제로 재밌어보여서 접근해보았다.

www.acmicpc.net/problem/20040

20040번: 사이클 게임

사이클이라 하니까 생각나는게 두가지였다. DFS/BFS로 사이클 판별, 오일러 경로. 

오일러 경로는 아래 문구 때문에 생각났다.

 

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

 

얼마 전에 오일러 경로를 공부해서 그런지 몰라도 오일러경로 또한 떠올랐다.

근데 오일러 경로는 특별한 알고리즘이라기보단, 베이스로 깔고 가는 느낌이어서

일단 DFS로 접근해보는 방법을 생각해보았다.

근데 N, M 범위 보는 순간..ㅋㅋ

---

의식의 흐름 및 해설

위에서 말했다시피 DFS로 생각해보았다. M번 만큼 for문을 돌고, 숫자 두 개가 불리면 양방향으로 연결지어 매번 dfs로 확인해보는 방법을 생각해보았다. 그런데, 이 문제... N<=5e5, M<=1e6이다. M번만큼 dfs로 확인해본다면 O(NM)으로 시간초과가 뜬다. 

 

그래서 잘 생각해보다가, 유니온 파인드가 생각났다. 

일단 시간복잡도도 O(MlgN) 정도라 통과가 가능하기 때문에 시간초과를 겪을 일은 없다고 판단.

유니온 파인드 또한 같은 집합인지 판별해주는 자료구조가 아닌가.

그런데, 0-1, 1-2, 2-3, 3-4 이런 경우는 사이클은 아닌데 같은 집합이니까 find(a)==find(b)여도 문제가 생기지 않을까 생각했었다.

 

그런데 생각해보니까 사이클일 경우는 이미 같은 집합일 경우에 또 연결해버리는 경우이므로 아래와 같이 코드를 짜면 되겠다 생각했었다. (트리의 가지 개수가 N-1개인 걸 생각해보면 좀 더 쉬울 것이다)

for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		// 이미 같은 집합인데 또 연결해버리면 사이클 생성
		if (find(a) == find(b)) {
			cout << i << "\n";
			return 0;
		}
		merge(a, b);
	}

이렇게 코드를 짤 경우, i번째가 사이클일 때 바로 i를 출력해주고 종료시켜주면 되겠다.

---

내 제출현황

이걸 왜 올렸냐 묻는다면,

내 코드가 짧기도 하고, 시간도 굉장히 준수하고, 무엇보다 한번에 맞춘 문제가 오랜만이라서 올렸다.

(아니 그럼 그냥 자랑하려고 올린거잖아)

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 500001;
int N, M, p[MAX];
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		p[i] = i;
	}
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		// 이미 같은 집합인데 또 연결해버리면 사이클 생성
		if (find(a) == find(b)) {
			cout << i << "\n";
			return 0;
		}
		merge(a, b);
	}
	cout << 0 << "\n";
}

---

재밌는 문제였다.

내일은 뭐풀지?