백준 20040번 사이클 게임 / C++ / 유니온 파인드(Union-Find)

알고리즘 개념: 유니온-파인드

유니온 파인드에 대해 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.

[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법

[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법

 

백준 20040번 사이클게임 

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

예제 보려면 더보기 클릭

예제 입력 1

6 5
0 1
1 2
2 3
5 4
0 4

예제 출력 1

0

예제 입력 2 

6 5
0 1
1 2
1 3
0 3
4 5

예제 출력 2

4

---

문제풀이

처음엔 문제를 해석하는게 좀 어려웠는데 간단하게 생각해보면 간단한 문제였다.

매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이미 그린 다른 선분과 교차하는 것은 가능하다.

-> Union으로 연결한다. 

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

-> Find로 찾는다. 

아주 간단하게 보면 Union-Find로 구현하면 간단히 끝날 문제라 볼 수 있다. 

 

Union과 Find를 구현한 함수는 Union-Find 개념에 설명이 올라와 있다. 

Find 연산 구현

int find(int n) {
	if (p[n] == n) return n;
	else return find(p[n]);
}

Union 연산 구현

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    else p[b] = a;
 }

 

그럼 이제 입력해서 연산을 처리하는 과정을 보자

a와 b를 입력해서 만약 a와 b의 루트노드가 같다면(이미 같은 부분배열에 속해있다면) 사이클이 형성 된 것이다. 

둘이 같은 부분배열이 아니라면 둘을 이어주는 코드 merge(a,b) 즉, 유니온을 실행해 둘을 합친다. 

for (int i = 0; i < m; i++) {
	cin >> a >> b;
	if (ans != 0) continue;
	if (find(a) == find(b)) {
		ans = i + 1;
	}
	else
		merge(a, b);
}

여기서 ans를 처음 사이클이 만들어진 번호 (해당 코드에선 i가 0부터 시작했으므로 i+1번) 으로 초기화 하고 나면

if (ans != 0) continue; 코드를 실행하여 입력만 받고 더 이상 합치거나 ans값이 변하는 일이 없도록 구현하였다. 

 

지금까지 봤던 코드를 합치면 다음과 같다. 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define INF 500005
using namespace std;
using ll = long long int;
int p[INF];
int n, m;
void fillp(int n) {
	for (int i = 0; i <= n; i++) 
		p[i] = i;
}
int find(int n) {
	if (p[n] == n) return n;
	else return find(p[n]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[b] = a;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	fillp(n);
	int a, b;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (ans != 0) continue;
		if (find(a) == find(b)) {
			ans = i + 1;
		}
		else
			merge(a, b);
	}

	cout << ans << "\n";


}