[자바]백준 10775번 공항 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

분리 집합 (Disjoint set, 서로소 집합)이란!?

Disjoint set은 서로 중복되지 않는 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰때 유용하게 쓰인다.
분리집합은 자식 노드가 부모 노드를 가리키는 형태이다.
분리집합 구현과 연산은 Union-Find알고리즘을 사용한다.

 

문제

오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.

비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

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

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 분리 집합

 

문제 설명

공항이 있고 공항마다 게이트가 1~G번 까지 있다.

비행기가 도착하면 게이트에 도킹해주고, 그 다음 비행기가 도킹할 게이트가 없으면 공항은 영업 종료 한다.

즉, 그 뒤부터는 남는 게이트가 있어도 더이상 비행기 도킹을 안한다는 말이다.

 

예를 들어 1번, 3번 게이트 도킹 완료, 2번 게이트는 비어있다고 가정하면, 다음 비행기가 1번 게이트에만 도킹이 가능하면 공항은 영업종료하고 그 뒤에 2번 게이트에 도킹 가능한 비행기는 도킹을 할 수 없다는 말이다.

 

입력줄 보면 셋째줄 부터 비행기가 들어갈 수 있는 게이트인데 4는 1~4에 도킹 가능하다는 말이다.

 

해설

해당 문제는 그리디 알고리즘 + 분리 집합을 사용하여 풀 수 있다.

 

• 그리디로는 비행기가 들어오는 순간순간을 계산하며,  비행기는 게이트가 큰 번호부터 도킹시도한다.
• 분리 집합으로 게이트에 비어있는 게이트를 연결하여 다음 비행기가 어디 게이트로 도킹을 시도 해야하는지 남는 게이트가 있는지 파악할 수 있게 해준다.

 

분리 집합을 어떻게 사용할지 예시를 들어보겠다.

1번, 2번, 3번 게이트가 있다고 가정하자.

1. 1번~3번 게이트에 도킹 가능한 비행기가 3번 게이트에 도킹을 시도했는데 3번 게이트가 비어져 있어서 도킹을 하였다. 
2. 또 다른 1번 ~ 3번 게이트에 도킹 가능한 비행기가 3번 게이트에 도킹을 시도할려고 했는데 2번 게이트로 가라고 게시판에 적혀있어서 2번 게이트에 도킹을 하고, 3번 게이트는 게시판에 1번 게이트를 사용하라고 변경된다.
3. 또 다른 1번 ~ 3번 게이트에 도킹 가능한 비행기도 3번게이트에 가서 게시판을 보고 1번 게이트에 도킹을 하게 된다.

분리 집합은 이 문제에서 게이판 게시판 같은 역할을 해주는것이다.
도킹이 완료되면 도킹 가능한 번호를 게시판에 초기화 해주는 것이다. 

 

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

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

        int G = Integer.parseInt(br.readLine());
        int T = Integer.parseInt(br.readLine());
        
        gates = new int[G + 1];
        for (int i = 1; i < gates.length; i++) {
            gates[i] = i;
        }
        
        int cnt = 0;
        for (int i = 0; i < T; i++) {
            int gi = Integer.parseInt(br.readLine());
            int ap = find(gi);

            if (ap == 0) {
                break;
            }
            
            int bp = find(ap - 1);
            
            if (ap != bp) {
                union(ap, bp, gi, ap - 1);
            }
            
            cnt++;
        }

        bw.write(cnt + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    
    public static void union(int ap, int bp, int a, int b) {
        int max = Math.max(ap, bp);
        int min = Math.min(ap, bp);
        gates[max] = min;
        find(Math.max(a, b));
    }
    
    public static int find(int a) {
        if (gates[a] == a) return a;
        
        return gates[a] = find(gates[a]);
    }
}

 

코드 설명

union-find 알고리즘 코드중에 union 부분의 코드가 좀 다른데, 보통 알려져 있는 코드는 저기 알고리즘이 끝난 후에 데이터를 살펴보면 gates(parents) 노드들을 담은 배열이 어중간하게 초기화가 되어있다.

예를들어 아래와 같은 코드가 일반적으로 쓰는 코드이다.

public void union(int a, int b) {
    int ap = find(a);
    int bp = find(b);
    
    if (ap != bp) {
        parents[ap] = bp;
    }
}

위의 코드로 문제를 풀고 데이터가 어떻게 초기화 되어있는지 살펴 보면 하나의 데이터가 연결 안된것 처럼 나온다.

예를 들어서 0, 0, 0, 3 이런식으로 4번째 노드만 0으로 연결이 안된것 처럼 나온다 물론 언젠가 find(4)로 실행하면 0으로 변경되면서 문제 푸는데는 문제가 없지만, 나는 내가 작성한 union-find 코드가 성능상 문제만 되지 않으면 계속 사용할 것이다.