[BOJ] 백준 10775 공항

출처:  https://www.acmicpc.net/problem/10775

 Input 

4

6

2

2

3

3

4

4

 

 Output 

3 

비행기가 연결(docking)하기 위해 주먹구구 방식으로 비어있는지 게이트를 찾고자한다면,

비행기와 게이트의 개수가 각각 1 ≤ N, M ≤ 105이므로 TLE(Time Limit Exceeded) 발생

※ Disjoint-Set & Union-Find 

Disjoint-Set & Union-Find

구현

Union-Find 알고리즘 이용해서 게이트의 도킹 가능 여부를 트리로 구성

* 다른 Union-Find 문제와 달리 0번째 노드 이용.

* union 연산할 때, 실제 도킹되는 곳을 찾습니다.

▷ gi번 게이트에 비행기 도킹 성공하면, union(find(gi), find(gi) - 1)

▷ gi-1번 게이트도 비행기가 도킹 성공하면, union(find(gi-1), find(gi-1) - 1)

 

시뮬레이션

▶ 4개의 게이트와 6개의 비행기가 존재.

 

▶ 첫번째 비행기를 g1 = 2번 게이트에 도킹 시도

union(find(2), find(2) - 1) = union(2, 1)

 

▶ 두번째 비행기를 g2 = 2번 게이트에 도킹 시도 

2번 게이트는 이미 도킹되었으므로 부모노드인 1번 게이트에 도킹

union(find(2), find(2) - 1) = union(find(find(1)), find(find(1)) - 1) = union(1, 0)

 

▶ 세번째 비행기를 g3  = 3번 게이트에 도킹 시도 

3번 게이트에 도킹은 성공했으며, 1~3번까지 모든 게이트가 도킹된 상태입니다.

 정점 [3]은 union 연산에 의해, 정점 [2]는 find 연산에 의해 정점[0]을 바라봅니다.

→ find[1] = find[2] = find[3] = 0 

 

▶ 네번째 비행기를 g4 = 3번 게이트에 도킹 시도 

1~3번까지 모든 게이트가 도킹되어 있으므로 종료.

find(g4) = 0 → 도킹 실패

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }
 
        int answer = 0;
        while(M-- > 0){
            int gate = Integer.parseInt(br.readLine());
             
            if(find(gate) == 0) break;
             
            answer++;
            union(find(gate), find(gate)-1);
        }
         
        // 정답 출력 
        System.out.println(answer);
    }
 
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        parent[a] = b;
    }
 
    private static int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }
}