[java] 20040번 사이클 게임

1. 문제 링크

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

2. 해결 방법 생각해보자 ...

유니온파인드 기법을 사용해서,
사이클이 생성되었을 때 출력하거나
M번째 차례가 끝나도 생성안되었으면 print 0

백준예시 1
초기값
각 노드들, parent[i] = i

1. 첫번째 판
   

2. 두번째 판
   

3. 세번째 판
   

4. 네번째 판
   

5. 다섯번째 판
   

처음 유니온 파인드 공부할 때 이해가 안갔었는데,
연결시켜줄 때 0 과 4를 연결시켜주는 것이 아닌
0의 루트노드와 4의 루트노드를 연결하는 것이기 때문에
0과 5를 연결시켜주는 것이다.
parent[5] = 0

여기서 만약 내가 수가 더 큰 수를 루트노드로 설정하고 싶다면?
0과 5를 비교해서 더 큰 수 parent[0] = 5 로 만들어주면 되는 것
이건 싸이클이 없는 경우고, 백준 예제 2를 통해서 보면

예제2
1. 첫번째판 0과 1을 합쳐준다

2. 두번째판 1과 2를 합쳐준다
   근데 여기서 1의 부모가 0 이므로, 2를 1의 부모와 합친다.
   

3. 세번째판 1과 3을 합쳐준다.
   

4. 네번째판 0과 3을 합쳐준다.

어라? 근데 위 이미지를 참고하면 이미 합쳐져있다.

💡 그러므로, 들어온 두 숫자들의 루트노드가 같을 때
즉 0의 루트노드 = 0 , 3의 루트노드 = 0 인 순간이 싸이클이 만들어지는 순간인 것이다.

따라서 싸이클이 생성 되었을 때 == 부모노드가 같을 때,
union 부분의 부모 노드가 같은 지 확인하는 함수에서 ( 제 코드에서는 a == b) 리턴해주면 된다 !

3. 코드

import java.io.*;
import java.util.*;

public class Main {

	static int N,M;
	static int[] parent ;
	static boolean CycleCheck;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		parent = new int[N];

		for(int i=0;i<N;i++)parent[i] = i;

		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			union(a,b,i);
			if(CycleCheck) return;
		}
		System.out.println(0);
		}

		public static void union(int a,int b,int i){
			a = find(a);
			b = find(b);
			if(a==b){
				System.out.println(i+1);
				CycleCheck = true;
				return;
			}
			parent[b] = a;
		}

		public static int find(int idx){
			if(parent[idx] == idx) return idx;
			parent[idx] = find(parent[idx]);
			return parent[idx];
		}
}

느낀점

코테 준비하면서 제일 처음 만났던 어려운 문제가 유니온 파인드였다.
그 땐 진짜 이해도 안가고 이런 어려운 알고리즘이 ㅇ.ㅇ....!! 이랬는데,
계속 원리 이해해보고 그려보고 백준 연습문제 풀어보고 하다보니
어느정도 개념도 정리되고 응용도 되는 것 같다.

알고리즘 문제.. 이렇게 한 단계씩 성장해나가는 맛에 푸는 거구나..
맛들려버렸다 🥰🥰🥰 정답입니다 !! 떴을 때가 제일 재밌고 뿌듯해 !!