[백준] Q10775 공항 JAVA

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

10775번: 공항

1. 문제의 유형 및 이해

그리디, disjoint set

공항에는 G개의 게이트가 있고 1부터 G까지 번호를 가진다.

P개의 비행기가 '순서대로' 도착하고, i번째 비행기를 1번부터 g번 게이트 중 하나에 영구적으로 도킹하려고 한다.

비행기가 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

가장 많은 비행기를 도킹시키고자 할 때 최대 몇대 도킹 시킬 수 있는가.

 

어떤 g번 게이트에 비행기가 도착할 때 1~g사이에 넣어주어야합니다.

g번 게이트 이미 차있다면 1~g사이에 넣을 수 있는 게이트에 넣어주어야 합니다.

게이트를 최대한 활용하여 최대한 가득 채울 수 있도록 순간 순간 최선의 선택을 하게 되면 가장 많은 비행기를 도킹시킬 수 있다고 생각하여 그리디알고리즘이라고 생각했습니다.

2. 문제 접근 방법

어떤 비행기가 g게이트에 도킹하려고 할 때 g번 게이트가 이미 차있다면 어디로 가는 것이 최적일지 생각해보았을 때 g번 게이트와 가장 가까운 곳에 도킹하여야 합니다.

게이트가 가능하다면 1 불가능하다면 0이라고 생각해보고 다음의 예시를 생각해봤습니다.

1 1 1 1 1 일 때, 4 - 4- 2 순으로 비행기가 들어왔습니다.

처음에는 4번 gate가 가능하니까 1 1 1 0 1 이 됩니다.

이후에 들어오는 4번 gate를 원하는 비행기가 가능한 범위는 1~4인데 4번 gate가 불가능하기 때문에 1~3번 게이트 중 하나를 골라야합니다. 이후에 4번보다 낮은 번호의 비행기가 들어온다면 이 비행기를 위해 최대한 게이트를 열어두어야 하기 때문에 3번 게이트를 선택하는 것이 최선의 선택입니다.

 

핵심은 가능한 게이트를 빠르게 찾는 방법이었습니다. 만약 가장 단순하게 4번 gate가 불가능 할 때, 다음의 gate를 찾기 위해 1~3번 게이트를 모두 확인한다면 매우 많은 시간이 걸리게 됩니다. 

문제에서 주어진 조건이 10^5이기 때문에 만약, 모든 gate가 10^5에 대해 들어오게 된다면 

0칸 1칸 2칸 ... $10^{15}$까지 모두 확인해야 되는 비효율적인 상황이 발생합니다.

 

그래서 결국 하고 싶었던 것은 '이 게이트로 왔을 때 다음에 x로 가시면 됩니다'를 구현하고 싶었었고, 

같은 질의에 대해 응답하기 위해 세그먼트 트리 등을 생각해보았는데 범위에 대한 질의가 아니라는 점에서 구현하기 힘들었습니다.

 

자세히 보면 결국 어떠한 group이 형성되게 된다는 것을 알 수 있습니다.

처음에는 [1][2][3][4][5] 와 같은 식이다가 2번에 들어오게 되면 

[1,2]와 같이 묶이게 되고 4번 게이트에 들어오게 되면 [1,2][3,4]와 같이 묶이게 됩니다.

이 [a,b]의 뜻은 b로 오면 a에 넣으세요 라는 의미를 갖고 있습니다.

여기서 만약 또 4번 게이트로 들어오게 되면 3번게이트에 넣게되고 이후 [1,2,3,4]와 같이 묶이게 되서

4번이나 3번 또는 2번게이트로 들어오면 1번 게이트로 가서 넣으세요 라고 하는 '다음에 어디로 가세요'를 구현할 수 있게 됩니다.

 

여러 gate들에 대한 update를 pointing만 바꾸는 개념과 grouping이라는 개념으로 한번에 해결할 수 있습니다.

package solvedac.level5.gold2;

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

/**
 * @author : pcrmcw0486
 * @문제번호 : Q10775
 * @문제이름 : 공항
 * @난이도 : Gold II
 * @date : 2022-02-15 오전 11:47
 * @문제이해 G개의 게이트 1에서 G까지 번호를 가짐.
 * P개의 비행기가 순서대로 도착할 예정
 * i번째 비행기를 번부터 g 번째 게이트 중 하나에 영구적 도킹
 * 도킹할 수 없다면 폐쇄됨.
 * 비행기를 최대 몇대 까지 도킹시킬 수 있는가?
 * G<=10^5// P<=10^5
 * 비행기를 주어지는 1 ~g 까지중 하나에 넣고 싶다.
 * @알고리즘 query 처리
 * 최대한 많이 넣어야함. 그리디.
 * 그리디
 * @접근방법 순서, 범위. query? 넣을 수 있는가?
 * Naiive하게 접근하면 O(GP) 10^10
 * 최적화를 해보자.
 * 세그먼트 트리 '누적합 + 질의 최적화" (실패)
 * Disjoint set
 * <p>
 * (실패)
 * 어떠한 query를 날려서 그 안에 가능한가를 하고 싶어
 * 세그먼트 트리를 사용하였는데, 이 때도 역시
 * 2 2 1이라면 0 2 0 0 0 0 0 이되서 [1,2]에 대한 질의는 잘 되지만
 * [1,1]이 되면 못찾아 낸다. 결국, 어디에 다음에 어디로 가야하는가를 어떻게 구하는가에 대한 문제엿다.
 * <p>
 * 그리디라는 접근 방법은 맞았고 이 방법에 집중했어야햇는데 true false에 집중한거같기도 하다.
 * 여튼, 처음 생각한것과 비슷하다.
 * 1 2 3 4 5 6 7 8 9 에서 2가 두번 들어올 때 다음 확인할 곳이
 * 1 0 3 4 5 6 7 8 9라 0이 되기 때문에 안되는데, 이렇게 되면 1이 update가 되지 않는다.
 * 이를 업데이트 하기 위해 2가 줄때 (2-1)과 같이 연결해놓고
 * 다음에 2가또 들어오면 (2-1-0) 이 되면 된다. 즉, union&find로 연결해주면 된다는 뜻이다.
 * 바로 밑 자식이 가야할 곳만빠르게 찾을 수 있다면 된다.
 */
public class Main {

    static int[] nextGate;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int G = Integer.parseInt(br.readLine());
        int P = Integer.parseInt(br.readLine());
        int cnt =0;
        //다음 가야할 gate위치
        nextGate = new int[G + 1];
        for(int i =0;i<G+1;i++) nextGate[i] = i;
        for (int i = 0; i < P; i++) {
            int target = Integer.parseInt(br.readLine());
            //가능한 게이트 찾기
            int possibleGate = findNextGate(target);
            //gate를 찾았는데 0번게이트라면 더이상 넣을 곳이 없다는 의미.
            if(possibleGate ==0) break;
            union(possibleGate-1,possibleGate);
            cnt++;
        }
        System.out.println(cnt);
    }
    public static int findNextGate(int x) {
        if(nextGate[x] == x) return x;
        return nextGate[x] = findNextGate(nextGate[x]);
    }
    public static void union(int a, int b) {
        a = findNextGate(a);
        nextGate[b] = a;
    }
}

3. 얻어가는 점

disjoint set에 대한 스킬을 얻어가는 것 같습니다.. 사실 disjoint set알고리즘 자체는 그렇게 어렵지 않았고,

지금까지 문제를 풀면서 '그룹' 또는 비슷한 결의 문제일 때 바로 캐치가 가능했었는데, 이번 문제를 통해

disjoint set에 대한 새로운 눈을 뜬 것 같습니다.

그룹을 만든다는 개념과 더해서 한번에 update가 가능하다는 점에 대해 한번더 생각할 수 있었습니다.