[JAVA]백준 20040번: 사이클 게임

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

20040번: 사이클 게임

1. 문제 설명

 

문제 요구사항

• 0부터 n-1까지 고유한 번호가 부여된 평면상의 점 n개가 주어지고, 이 중 어느 세 점도 일직선 위에 놓이지 않는다.
• 매 차례마다 두 점을 선택해서 이를 연결하는 선분을 긋는다. 이전에 그린 선분을 다시 그릴 수 없다.
• 게임을 진행하다가 처음으로 사이클이 생성되는 순간 게임은 종료된다.
• 점의 개수 n : 3<=n<=500,000
• 진행된 차례의 수 : 3 <=m <=1,000,000

출력 요구 사항

• 사이클이 완성되었는지 판단
• 사이클이 완성되었다면 몇 번째 차례에 처음으로 사이클이 완성된 것인지 출력

 

2. 풀이

 

Union Find 알고리즘으로 해결할 수 있다.

 

사이클이 처음으로 생성되는 순간은 이미 부모로 이어진 두 개의 점끼리 연결되는 순간이다.

 

이를 이용하여 점 X의 부모를 저장하고, 두 점 A, B의 최상단 부모가 같을 때까지 게임을 반복한다.

 

시간을 단축하기 위해 경로 압축과 rank를 사용했다.

 

1. 경로 압축

탐색을 진행할 때마다 X의 바로 앞 부모를 가리키는 것이 아니라 X의 최상단 부모를 가리키게 바꾸어 경로를 압축한다.

 

2. rank

높이가 더 큰 집합에 높이가 더 작은 집합을 더한다.

 

 

3. 코드

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

public class Main {

    public static int[] parent;
    public static int[] rank;

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

        int dotNum, orderNum;
        int answer = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        dotNum = Integer.parseInt(st.nextToken());
        orderNum = Integer.parseInt(st.nextToken());

        parent=new int[dotNum];
        rank = new int[dotNum];

        // parent 초기화
        for (int x = 0; x < dotNum; x++) {
            parent[x] = x;
        }

        // 조건 입력 받는 중
        for (int x = 1; x <= orderNum; x++) {
            int one = 0, two = 0;

            st = new StringTokenizer(br.readLine());

            one = Integer.parseInt(st.nextToken());
            two = Integer.parseInt(st.nextToken());

            // 사이클 생성
            if(!union(one,two)){
                answer = x;
                break;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();

    }

    // 집합 생성
    public static boolean union(int one, int two){
        int oneParent = findParent(one);
        int twoParent = findParent(two);

        if(oneParent==twoParent)
            return false;

        // 랭크가 더 높은 것에 낮은거 추가해야 함.
        // oneParent가 더 랭크가 높은 경우 swap
        if(rank[oneParent]>rank[twoParent]){
            int temp = oneParent;
            oneParent = twoParent;
            twoParent = temp;
        }else if(rank[oneParent]==rank[twoParent]){
            // 랭크가 같은 경우 rank+1
            rank[twoParent]++;
        }
        
        parent[oneParent] = twoParent;
        
        return true;
    }

    // 부모 찾기
    public static int findParent(int x){
        if(parent[x]==x)
            return x;
        else
            return parent[x] = findParent(parent[x]);
    }
}