P.10775 공항

코드

import java.io.*;

public class Main {

    static int g, p;
    static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        g = Integer.parseInt(br.readLine());
        p = Integer.parseInt(br.readLine());
        parents = new int[g + 1];
        for (int i = 0; i <= g; i++) parents[i] = i;

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

            int docking = find(airplane);
            if (docking == 0) break;
            union(docking, docking - 1);
            cnt++;
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    private static void union(int cur, int target) {
        cur = find(cur);
        target = find(target);

        if (cur != target) parents[cur] = target;
    }

    private static int find(int airplane) {
        if (parents[airplane] == airplane) return airplane;
        return parents[airplane] = find(parents[airplane]);
    }
}

코드 설명

n번째 비행기가 여러 개 있을 때, 첫 비행기는 n번째 게이트를 점유할 수 있지만 다음 게이트는 그것보다 작은 게이트를 이용해야만 한다.

따라서 게이트를 점유하는 비행기가 있다면 앞선 게이트들을 브루트포스하는 방법을 이용할 수 있다.

하지만 시간은 1초이고 게이트는 최대 10,000개이기 때문에 10,000 게이트를 이용하고 싶은 비행기가 10,000대가 있다면 이 방법으로는 1초내에 풀 수 없다.

 

그럼 이 브루트포스 접근법에서 조건은 무엇이었을까?

해당 게이트가 점유 상태라면 이전 게이트를 확인해야 한다.

 

브루트포스에서는 이전 게이트를 모두 확인했을 때 시간초과가 발생하였으므로, 해당 게이트에서 바로 이용할 수 있는 게이트로 접근할 수 있는 방법을 찾아야 한다.

이는 병합 과정을 거친다는 의미이므로 Union-Find를 이용했다.

 

1. 이용할 수 있는 게이트 확인

먼저, parent함수는 현재 게이트(idx)에서 접근할 수 있는 게이트 번호를 나타내며 idx로 초기화된다.

parents = new int[g + 1];
for (int i = 0; i <= g; i++) parents[i] = i;

 

이후, find함수를 이용해 해당 게이트를 이용할 수 있는지 확인한다.

리턴값이 0이라면 이용할 수 없다고 판단하며 종료한다.

게이트는 서로 이어지며 병합된다고 가정하기 때문에 0이 반환될 경우 이전 게이트 또한 이용할 수 없다는 의미이다.

int airplane = Integer.parseInt(br.readLine());

int docking = find(airplane);
if (docking == 0) break;

private static int find(int airplane) {
    if (parents[airplane] == airplane) return airplane;
    return parents[airplane] = find(parents[airplane]);
}

---

만약 2번 게이트를 이용하려는 비행기가 2대라고 가정해보자.

parent[5]배열은 다음과 같이 초기화가 되어있다.

0	1	2	3	4
0	1	2	3	4

 

처음 비행기가 2번 게이트를 이용하려고 했을 때, parent[2] = 2이므로 2번 게이트를 사용할 수 있다.

(이후 parent는 다음과 같이 변경되는데 이 과정은 union함수에서 설명함)

0	1	2	3	4
0	1	1	3	4

2번 게이트가 1로 변경됐다.

2번 게이트를 이용하려고 할 시 1번 게이트로 바로 도킹을 시켜준다.

다음 비행기가 2번 게이트를 이용하려고 했을 때, parent[2] != 2이므로 find(1)을 수행하게 되며 1번 게이트를 반환한다.

 

2. 이용할 수 있는 게이트 변경

union(docking, docking - 1);

private static void union(int cur, int target) {
    cur = find(cur);
    target = find(target);

    if (cur != target) parents[cur] = target;
}

위의 find 후 parent 배열이 변경되는 것은 union함수에서 수행한다.

받은 게이트 값과 이전 게이트 값을 병합하는 과정이다.

받은 게이트 값의 부모(게이트)를 이전 게이트로 변경해줌으로써 이전 게이트와 병합할 수 있다.