[백준 10775] 공항(Java)

문제 링크 : https://www.acmicpc.net/problem/10775

이 문제는 그리디 알고리즘과 유니온 파인드를 이용하여 풀 수 있습니다.

우선 들어오는 비행기의 숫자값이 클수록 가장 뒤의 게이트부터 앞쪽 순서대로 채워넣는 방식으로 비행기를 할당할 수 있습니다. 예를 들어 비행기 입력값이 4라면 4번째 게이트를 우선적으로 채우고 만약 4번째 게이트가 찼다면 3번째, 3번째도 찼다면 2번째.. 이런 식으로 그리디 알고리즘을 적용합니다.

이 때 게이트가 찼는지 확인하는 것을 유니온 파인드로 구현합니다. 더 정확히는 현재 비행기 값이 가리키는 게이트가 향할 수 있는 게이트 넘버라고 보시면 됩니다. 만약 4번째 게이트가 찼다면 parent 배열의 값을 3으로 조정합니다. 만약 3도 이미 차있는 상태라면 3번 게이트의 parent값은 2를 가리키게 되므로 4번 게이트의 parent값은 2가 됩니다.

따라서 유니온 파인드로 현재 비행기 입력값의 parent값, 즉 현재 비행기 입력값이 향할 수 있는 게이트 넘버를 이전 게이트 넘버와 합치는 방식으로 구현하고, 가리키는 넘버가 0일 경우 더 이상 채울 수 없으므로 break 합니다.

다음은 코드입니다.

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

class Main{
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int G = Integer.parseInt(br.readLine());
        parent = new int[G+1];
        for(int i=0;i<=G;i++) parent[i] = i;

        int P = Integer.parseInt(br.readLine());
        int idx = 0;
        for(idx=0;idx<P;idx++){
            int curr = Integer.parseInt(br.readLine());
            int gate = find(curr);
            if(gate == 0) break;
            union(gate-1,gate);
        }
        System.out.println(idx);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b) parent[b] = a;
    }

    static int find(int a){
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }
}