BOJ - 공항(10775)

문제(링크)


기본적인 유니온-파인드 알고리즘의 findI(), union() 함수는 그대로 사용하는데,
어떤 걸 노드로 정하고 언제 union 할지가 까다로운 문제였습니다.

가장 최선의 방법은 gi = n 일 때,  n번째 공항에 가장 먼저 도킹하는 것입니다.
만약 n번째 공항이 이미 도킹되었다면 n - 1, n - 1 번째도 도킹되었다면 n - 2 ...
과 같은 식으로 도킹해주면 최대값을 구할 수 있습니다.

즉, n -> n-1 -> n-2 -> n-3(Root) 이런 식으로 union을 해주면 다음 n 이라는 노드가 들어왔을 때 n의 Root 노드를 찾고, 그 노드의 -1 번째 노드와 다시 union을 해주는 식으로 풀이하면 됩니다.
만약 Root가 0 이라면 비어있는 게이트가 없는 것이므로 중단합니다.

import java.io.*;

public class Main {

    public static int G, P;
    public static int[] parent;
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        G = Integer.parseInt(br.readLine());
        P = Integer.parseInt(br.readLine());

        parent = new int[G + 1];

        for (int i = 0; i <= G ; i++) {
            parent[i] = i;
        }

        int cnt = 0;
        for (int i = 0; i < P ; i++) {
            int now = Integer.parseInt(br.readLine());

            int p = find(now);
            if(p != 0){
                union(p, p - 1);
                cnt++;
            }
            else
                break;
        }
        System.out.println(cnt);
    }
    public static int find(int now){
        if(now == parent[now])
            return now;
        return parent[now] = find(parent[now]);
    }
    public static void union(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y)  return;
        parent[x] = y;
    }
}