[BOJ] 백준 10775 - 공항 풀이

1. 문제

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

10775번: 공항

2. 풀이

• 하나의 비행기는 1~자기 자신까지의 게이트에 도킹할 수 있지만, 최대한 많은 비행기를 도킹하기 위해선 주어진 수 범위의 수 중 최대한 큰 수의 게이트에 도킹해야 한다.
• 게이트 수 G가 최대 10 ^ 5개, 비행기의 수가 최대 10 ^ 5개이므로 단순 반복문(O(n^2))으로는 해결할 수 없다.
• 제한시간인 1초에 맞추기 위해선 log N의 시간 복잡도를 가져야 하므로 "분리 집합"으로 해결해야 한다.
• Union - Find 방법
  • 이 문제에서 부모 배열 = 이 인덱스에 맞는 비행기가 도착할 때 도킹할 수 있는 게이트의 번호를 저장한 배열
  • 이를 위해 입력으로 주어진 수를 Find()를 통해 도킹할 수 있는 게이트를 찾는다.(부모를 찾는다.)
  • 만약 Find()를 통해 찾는 값이 0이라면 더 이상 도킹할 수 없다는 의미이므로 로직을 종료한다.
  • 만약 Find()를 통해 찾은 값이 0이 아니라면 그 게이트에 도킹하고 그 값에 -1을 한 값과 Union한다.
    
    
    
    

3. 소스 코드

import java.io.*;

public class Main {
    static int G, P;
    static int[] paraent;
    static boolean[] visited;
    static int result = 0;
    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());

        // make -set
        paraent = new int[G + 1];
        for (int i = 1; i <= G; i++) {
            paraent[i] = i;
        }

        // 방문배열 초기화
        visited = new boolean[G + 1];

        // 도킹시키는 비행기 입력
        for (int i = 0; i < P; i++) {
            // 비행기 번호
            int idx = Integer.parseInt(br.readLine());

            int fIdx = Find(idx);
            if (fIdx == 0) {
            	break;
            } else {
            	Union(fIdx - 1, idx);
                result++;
            }
        }
        
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    // 유니온
    private static void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);

        if (px > py) {
            paraent[px] = py;
        } else if (py > px) {
            paraent[py] = px;
        }
    }

    // 파인드
    private static int Find(int x) {
        if (paraent[x] == x) {
            return x;
        }

        return paraent[x] = Find(paraent[x]);
    }
}

4. 배운점

• Union-Find 문제를 많이 풀어보자
• 분리 집합은 여러 노드를 같은 집합으로 묶는다는 것을 기억하자
  
  
  
  

5. 점수

70 / 100