[백준 10775] - 공항

 

문제

• 오늘은 신승원의 생일이다.
  • 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
• 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
  • 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 \(\mathrm{g}_{i}\) (1 ≤ \(\mathrm{g}_{i}\) ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.
  • 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.
• 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다.
• 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다.
  • 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

입력

• 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ \(10^{5}\))가 주어진다.
• 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ \(10^{5}\))가 주어진다.
• 이후 P개의 줄에 \(\mathrm{g}_{i}\) (1 ≤ \(\mathrm{g}_{i}\) ≤ G) 가 주어진다.

 

출력

• 승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

솔루션

• Disjoint Set을 이용한 문제이다.
  • Disjoint Set
• 문제의 핵심은 입력으로 주어지는 각 번호 게이트 집합의 루트 게이트가 0이 아니라면, 현재 게이트 이하의 번호에서 도킹할 수 있는 게이트가 있다는 것이다.
  • 현재 도킹할 수 있는 게이트가 있다면, 현재 입력된 번호 게이트가 속한 루트 게이트를 찾고 루트 게이트 번호 보다 1 낮은 번호 (루트 게이트 번호 - 1) 게이트와 합집합 연산을 수행한다.
• 이런식으로 진행되면 결국 현재 번호 게이트 이하 게이트에서 도킹할 곳이 없을 경우, 루트 게이트 번호로 0을 반환할 것이다.

예시 1 : 4 1 1

예시 2 : 2 2 3 3 4 4

• 비행기는 순서대로 도착해야 하며, 4번째 비행기 3이 도착하지 못했기 때문에 이후의 비행기는 고려하지 않는다.

 

Code

• 전체 코드 : Solution_10775

노드가 속한 집합의 루트 노드를 반환해주는 함수

public static int Find(int u) {
    if (parent[u] == u)
        return u;
 
    return parent[u] = Find(parent[u]);
}

 

두 노드가 속한 집합을 합쳐주는 합집합 연산 함수

public static void Union(int u, int v) {
    int uR = Find(u);
    int vR = Find(v);
 
    if (uR == vR)
        return;
 
    if (rank[uR] > rank[vR])
        Swap(uR, vR);
 
    parent[uR] = vR;
 
    if (rank[uR] == rank[vR])
        rank[vR]++;
 
}

 

각 노드의 루트 노드를 초기화 하는 함수

public static void Initialize() {
    for (int i = 1; i <= G; i++)
        parent[i] = i;
}

 

메인 함수

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());
    int P = Integer.parseInt(br.readLine());
    int count = 0;
    boolean stop = false;
 
    parent = new int[G + 1];
    rank = new int[G + 1];
 
    Initialize();
 
    for (int i = 0; i < P; i++) {
        int g = Integer.parseInt(br.readLine());
 
        int p = Find(g);
 
        if (p != 0) {
            Union(p, p - 1);
            count++;
        } else
            break;
    }
 
    bw.write(count + " ");
    bw.flush();
    bw.close();
    br.close();
}

 

결과