[알고리즘] 백준 10775 공항 -유니온파인드- 자바 코틀린

 

 

www.acmicpc.net/problem/10775

10775번: 공항

 

 

 

 

백준 공항 문제를 풀어봤습니다. 백준 유형별문제에서 유니온파인드 문제를 골라푼거라 접근을 쉽게 할 수 있었습니다. 

 

해결방법을 요약하면,

1. Gi 비행기는 자신과 같거나 작은 게이트번호에만 도킹할 수 있다.

2. 그러므로 최대한 많은 비행기를 도킹시키려면 자신이 현재 도킹될 번호 -1 로 union을 해주며 추가 도킹한다. (이때 도킹될 번호는 find를 사용하면 된다.) 도킹이 가능했다면 답(answer)를 +1 해준다.

3. 이후 더이상 도킹될 장소가 안되면 0을 바라보게 될 것이다. 이때 break 해서 답 출력

 

동그라미가 parent (상호배타적집합) , 네모안이 게이트라고 치면 예제2의 순서는 다음과 같습니다. 존못그림은 양해부탁드립니다. 

 

 

풀이는 다음과 같습니다.

 

 

[Java]

import java.util.Scanner;

class Main {
    private static int G; // G개의 게이트
    private static int P; // P개의 게이트
    private static int[] parent;
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        G = sc.nextInt();
        P = sc.nextInt();
        parent = new int[G + 1];
        for (int i = 1; i <= G; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= P; i++) {
            int gate = sc.nextInt(); // 게이트 번호
            int docking = find(gate); // 도킹될 번호 (0이면 더이상 도킹 불가하므로 폐쇄)
            if (docking == 0) break;
            answer++;
            union(docking, docking - 1); // 다음번 중복 도킹방지를 위해 자신보다 낮은번호로 도킹되게끔 Union (최종적으론 0을 바라봄)
        }
        System.out.println(answer);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }

}

 

[Kotlin]

import java.util.*

private var G // G개의 게이트
        = 0
private var P // P개의 게이트
        = 0
private lateinit var parent: IntArray
private var answer = 0
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    G = sc.nextInt()
    P = sc.nextInt()
    parent = IntArray(G + 1)
    for (i in 1..G) {
        parent[i] = i
    }
    for (i in 1..P) {
        val gate = sc.nextInt() // 게이트 번호
        val docking = find(gate) // 도킹될 번호 (0이면 더이상 도킹 불가하므로 폐쇄)
        if (docking == 0) break
        answer++
        union(docking, docking - 1) // 다음번 중복 도킹방지를 위해 자신보다 낮은번호로 도킹되게끔 Union (최종적으론 0을 바라봄)
    }
    println(answer)
}

private fun union(x: Int, y: Int) {
    var x = x
    var y = y
    x = find(x)
    y = find(y)
    if (x != y) {
        if (x < y) parent[y] = x else parent[x] = y
    }
}

private fun find(x: Int): Int {
    return if (parent[x] == x) x else find(parent[x]).also { parent[x] = it }
}

 

오랜만에 유니온파인드 문제를 풀었는데 머리에 남아있어서 다행이었습니다.

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!