[BOJ 20040] 사이클 게임 (Java)

#문제

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

20040번: 사이클 게임

#풀이

M개의 선분이 주어지고 Cycle이 발생하는 순간의 차례를 리턴하는 문제이다. 

Union-find 기법의 대표적인 문제이다. 

• MakeSet(): parent, rank 초기값 설정
  • parent는 자기 자신, rank는 0으로 초기화
• Find(a): 원소 a의 parent node (root node)를 리턴
  • path-compression 기법으로 중간 가지를 없애고 parent로 root node를 저장하고 리턴하도록 구현
• Union(a, b): 원소 a와 b를 동일한 집합으로 묶는다.
  • rank가 큰 node가 작은 node의 parent가 되도록 설정
  • 만약 rank가 같다면 한쪽의 rank를 증가시켜 parent가 되도록 설정
  • 매개 변수 a와 b의 parent node로 관계 설정

 

#소스코드

package unionfind;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BOJ20040 {
    public static HashMap<Integer, Integer> parent;
    public static HashMap<Integer, Integer> rank;
    public static int N, M;
    public static int pro() throws Exception {
        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 HashMap<Integer, Integer>();
        rank = new HashMap<Integer, Integer>();
        makeSet();

        int answer = 0;
        for(int i = 1; i <= M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(find(a) != find(b)){
                union(a, b);
            } else {
                answer = i;
                break;
            }
        }
        return answer;
    }

    public static void makeSet(){
        for(int i = 0; i < N; i++){
            parent.put(i, i);
            rank.put(i, 0);
        }
    }

    public static int find(int a){
        if(parent.get(a) == a) return a;
        parent.put(a, find(parent.get(a))); // path-compression 트리를 납작하게 만들어주는 역할
        return parent.get(a);
    }

    public static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(rank.get(a) > rank.get(b)){
            parent.put(b, a);
        } else {
            parent.put(a, b);
            if(rank.get(a) == rank.get(b)){
                rank.put(b, rank.get(b)+1); // rank-compression
            }
        }
    }

    public static void main(String[] args) throws Exception {
        System.out.println(pro());
    }
}