[BOJ] 백준 20040 - 사이클 게임 풀이

1. 문제

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

20040번: 사이클 게임

 

2. 풀이

• Union-Find 알고리즘 사용
• 게임 당 입력을 받아서 Union-Find 함수를 사용하여 부모 노드를 갱신
• 핵심 포인트는 Find 함수를 실행했을 때 부모가 같다면 이는 사이클이 발생했다는 의미!!
  
• 주요 자료구조
  • int N : 노드수
  • int M : 간선 수
  • int[] parent : 각 노드의 부모를 저장할 배열
    
    
    
    

3. 풀이 Logic

• Make-Set을 통해 각 노드의 부모를 자기 자신으로 초기화
• 각 게임마다 입력을 받고 Union() 함수 시작
  • 입력받은 두 인자를 각각 find() 함수를 통해 부모를 찾는다.
  • 찾은 두 부모의 값을 비교하여 부모를 연결하고 true를 반환
    
    • 이때 find()를 한 두 부모가 같다면 이는 사이클이 생겼다는 의미이므로 false를 반환
  • 만약 union() 함수에서 false를 리턴 받았다면 그때의 게임 횟수를 result에 넣고 반복문을 끝낸다.
    
    
    
    

4. 소스 코드

import java.io.*;

import java.util.StringTokenizer;

public class Main {
    static int N; // 노드수
    static int M; // 간선 수
    static int[] parent; // 각 노드의 부모를 저장할 배열
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // make-Set
        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 x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 유니온
            if (!union(x, y)) {
                result = i + 1;
                break;
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    // 유니온
    private static boolean union(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px > py) {
            parent[py] = px;
            return true;
        } else if (px < py){
            parent[px] = py;
            return true;
        } else {  // 유니온을 했을 때 부모가 같으면 사이클이 발생한 것
            return false;
        }
    }

    // 부모를 찾는 find
    private static int find(int idx) {
        if (idx == parent[idx])
            return idx;

        return parent[idx] = find(parent[idx]);
    }
}

5. 점수

70 / 100