[BOJ 10775] 공항 (Java)

BOJ 10775 공항

난이도 : 골드 2

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

10775번: 공항

 

전략

비행기가 순서대로 주어지고, 중간에 한 비행기가 게이트와 연결되지 않으면 이후 비행기들이 연결될 수 없으므로

그리디 형태로 생각해야 한다.

각 비행기는 1<=gi 게이트 중 하나에 영구적으로 도킹하므로, 그리디로 접근했을 때

가장 많은 비행기를 연결하려면 도킹 가능한 게이트 중 가장 번호가 높은 것을 선택해야 한다. 

 

단순하게 끝난 것 같지만, 도킹 가능하면서 가장 번호가 높은 게이트는 어떻게 구할 수 있을까?

 

1. 도킹 가능할 때까지 번호를 내려오면서 탐색

 : 최악의 경우 O(GP), GP는 최대 10^10이므로 시간초과가 발생할 것이다.

2. 우선순위큐로 도킹된 게이트를 제거하면서 관리

 : 각 비행기마다 가능한 게이트의 범위가 다르기 때문에 (1<=gi) 일관된 우선순위를 만들 수 없다.

3. 다음 도킹 가능한 게이트의 번호를 가리키도록 분리 집합으로 구현

 : 도킹 가능한 게이트는 자기 자신을 가리키고, 도킹된 게이트는 도킹 가능한 게이트 중 가장 번호가 큰 것을 가리키도록

분리집합을 구현한다.

 

시행착오

시행 착오 없이 간단하게 풀려서 놀랐던 문제이다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

        int[] gates = new int[G + 1];
        for (int i=0; i<=G; i++)
            gates[i] = i;

        int cnt = 0;
        for (; cnt < P; cnt++) {
            int gi = Integer.parseInt(br.readLine());
            int idx = find(gates, gi);
            if (idx > 0) {
                gates[idx] = find(gates, idx - 1);
            }
            else
                break;
        }

        System.out.println(cnt);
    }

    static int find(final int[] gates, int i) {
        if (i <= 0)
            return -1;
        if (gates[i] == i)
            return i;
        return gates[i] = find(gates, gates[i]);
    }
}

분리집합에서 find 연산만을 이용했다.

도킹된 게이트는 도킹되지 않은 가장 큰 게이트를 가리키고 이것이 -1씩 내려가다가 0을 가리키게 되면

해당 게이트는 사용 불가하다.

따라서 그리디로 항상 최대의 비행기가 연결될 수 있도록 보장된다.

 

깨달은 점

분리집합 모르고 풀었으면 구현이 조금 복잡했을 것 같은데 union-find를 알고 푸니까 매우 간단했다.