[ 백준 ] 10775 공항

📌 Problem

입력으로 주어지는 항공기들이 순서대로 도착하며 각각 주어진 gi 값에 따라 최적의 게이트에 도킹한다. 도팅 할 수 있는 게이트가 없다면 공항은 추가적인 항공기들을 받을 수 없다. 즉, 입력 순서에 따라 처리해야 한다.

📌 Example

• Example 1
  이 문제는 union-find를 통해 해결하는 문제이다. 1번 문제를 예시로 들면 다음과 같다.
  
  각각의 게이트는 처음에 자기 자신을 가리킨다. 첫 번째로 들어오는 항공기는 gi = 4으로 게이트 1 ~ 4번에 모두 도킹 할 수 있다. 게이트는 큰 번호부터 도킹되고 도킹된 게이트는 게이트 번호 - 1번 게이트를 가리킨다. 첫 번째 항공기 이후의 상태는 다음과 같다.
  
  첫 번째 항공기는 4번째 게이트까지 도킹이 가능하고 4번째 게이트의 find 값은 G4 였기 때문에 G4는 G3로 union 하게 된다. 이를 해석하면 gi = 4인 항공기가 도킹할 수 있는 게이트는 G3부터 G1까지라는 것을 의미한다. Union-Find으로 해석하자면 find 값은 도킹 할 수 있는 게이트의 최댓값이다. find(gi) = GN이면 N번 게이트까지 도킹 할 수 있다.
  두 번째 항공기는 gi = 1이고 find(g1) = G1이기 때문에 G1은 G0를 가리키게 된다. (G0는 가상의 게이트이다.)
  
  세 번째 항공기는 gi = 1이고 find(g1) = G0이다. G0에 도킹해야 하지만 G0는 가상의 게이트이기 때문에 세 번째 비행기는 도킹할 수 없으며 공항은 폐쇄된다. 결과적으로 도킹된 항공기는 1번과 2번으로 2개이다.

• Example 2
  좀 더 자세한 이해를 위해 2번 예제를 봐보도록 하자. 2번 예제는 4개의 게이트와 6개의 항공기가 있다.
  
  1번 항공기는 gi = 2이다. find(G2) = G2이기 때문에 1번 항공기는 G2와 도팅하고 G2 -> G1으로 union한다.
  
  2번 항공기는 gi = 2이다. find(G2) = G1이기 때문에 2번 항공기는 G1과 도킹하고 G1 -> G0으로 union한다. 마찬가지로 G0는 가상의 게이트이다.
  
  3번 항공기는 gi = 3이다. find(G3) = G3이기 때문에 3번 항공기는 G3와 도킹하고 G3 -> G2으로 union한다.
  
  4번 항공기는 gi = 3이다. find(G3) = G0이기 때문에 4번 항공기는 도킹이 불가능하며 공항이 폐쇄되어 최대 3개의 항공기만 도킹이 된다. 그러므로 2번 예제의 정답은 3이다.

📌 Solution

먼저 게이트와 항공기의 수에 따른 자료구조를 초기화해야 한다.

int[] gates;
int count = 0;

gates는 각각의 게이트가 가리키는 gate이다. count는 도킹이 완료된 항공기의 수이다.

int GATE_NUM = Integer.parseInt(reader.readLine());
int PLANE_NUM = Integer.parseInt(reader.readLine());
gates = IntStream.rangeClosed(0, GATE_NUM).toArray();

gates는 처음에 자신을 가리킨다.

while (PLANE_NUM-- > 0) {
    int gi = Integer.parseInt(reader.readLine());
    int gate = find(gi);
    if (gate != 0) union(gate, gate - 1);
    else break;
}

각각의 항공기에 대한 gi 값을 차례대로 입력 받는다. 입력 받은 gi 값을 바탕으로 find함수를 실행한다. 이때 반환 받은 gate의 번호가 0번이면 도킹이 불가능하다는 것을 의미하므로 while 문을 종료시킨다. 만약 0이 아니면 union 함수를 통해 항공기를 도킹한다.

Union 함수와 Find함수는 각각 다음과 같다.

private int find(int gate) {
    return gate == gates[gate] ? gate : (gates[gate] = find(gates[gate]));
}

private void union(int gateA, int gateB) {
    gateA = find(gateA);
    gateB = find(gateB);
    gates[gateA] = gateB;
    count++;
}

📌 Code

int[] gates;
int count = 0;

void solve() throws IOException {
    int GATE_NUM = Integer.parseInt(reader.readLine());
    int PLANE_NUM = Integer.parseInt(reader.readLine());
    gates = IntStream.rangeClosed(0, GATE_NUM).toArray();

    while (PLANE_NUM-- > 0) {
        int gi = Integer.parseInt(reader.readLine());
        int gate = find(gi);
        if (gate != 0) union(gate, gate - 1);
        else break;
    }

    result.append(count);
}

private int find(int gate) {
    return gate == gates[gate] ? gate : (gates[gate] = find(gates[gate]));
}

private void union(int gateA, int gateB) {
    gateA = find(gateA);
    gateB = find(gateB);
    gates[gateA] = gateB;
    count++;
}