백준 10775 : 공항 - javascript(그리디 쌈박한 문제, Union-Find)

문제 출처 

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

 

정답 풀이 

 

사람들 천재야? 어떻게 이런 생각을 했는지 싶다 

그리디 참 쌈박한 문제다. 인정 !

 

- 그리디 알고리즘 

- 유니온 파인드 자료구조 

를 활용해서 풀 수 있다. 

 

각 게이트는 비행기를 수용할 수 있고, 가장 큰 번호의 게이트에 비행기를 도킹시켜야 최대한 많은 비행기를 도킹시킬 수 있다. 

 

1. Union-Find 자료구조

- find(x): x가 속한 집합의 대표자를 찾는다. 경로 압축을 사용하여 효율적으로 찾는다. 

- union(x,y): x와 y를 같은 집합으로 합친다.  

 

2. 그리디 

- find(gate) : 각 비행기에 대해, 해당 비행기가 도킹할 수 있는 가장 큰 번호의 게이트를 찾는다 

- union(availableGate, availableGate - 1): 해당 게이트에 비행기를 도킹시키고, 다음 비행기가 그 이전 번호의 게이트에 도킹할 수 있도록 게이트를 합친다. 

- 만약 더이상 도킹할 수 잇는 게이트가 없으면 (즉, availableGate가 0이 되면) 더이상 비행기를 도킹할 수 없으므로 반복을 중지한다. 

 

3. 시간 복잡도 

- Union-Find 자료구조를 활용하면 각 연산이 거의 O(1) 시간에 수행되므로, 전체 시간 복잡도는 O(P log G)정도가 된다. 

 

## Union-Find 자료구조

- 합집합-찾기 자료구조 

- 서로소 집합들을 효율적으로 관리하고, 합집합(Union) 및 특정 원소가 속한 집합을 찾는(Find) 연산을 빠르게 수행하기 위한 자료구조다. 

 

- 두가지 연산 제공 

  - Find(x): 원소 x가 속한 집합의 대표자(root 또는 parent)를 찾는다. 

  - Union(x, y): 두 원소 x와 y가 속한 집합을 하나의 집합으로 합친다. 

 

- 두가지 기법으로 최적화 

  - 경로 압축(Path Compression): Find 연산 시, 탐색 경로에 있는 모든 노드들이 직접 루트에 연결되도록 한다. 

  - 랭크 기반 합치기 (Union by Rank or Size) :Union 연산 시, 항상 높이가 낮은 트리를 높이가 높은 트리에 붙인다. 이를 통해 트리의 높이를 줄여 Find 연산의 시간 복잡도를 줄일 수 있다. 

정답 코드 

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size + 1 }, (_, i) => i);
    }

    find(x) {
        if (this.parent[x] === x) {
            return x;
        }
        return this.parent[x] = this.find(this.parent[x]);
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }
}

function solution(G, P, planes) {
    const uf = new UnionFind(G);
    let count = 0;

    for (let i = 0; i < P; i++) {
        const gate = planes[i];
        const availableGate = uf.find(gate);

        if (availableGate === 0) break;

        uf.union(availableGate, availableGate - 1);
        count++;
    }

    return count;
}

// 입력 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const G = parseInt(input[0], 10);
const P = parseInt(input[1], 10);
const planes = input.slice(2).map(Number);

console.log(solution(G, P, planes));

 

주석코드 

class UnionFind {
    constructor(size) {
        // parent 배열을 초기화하여 각 원소가 자기 자신을 부모로 가지도록 설정
        this.parent = Array.from({ length: size + 1 }, (_, i) => i);
    }

    // 원소 x가 속한 집합의 대표자를 찾는 함수 (경로 압축 사용)
    find(x) {
        if (this.parent[x] === x) {
            return x; // x가 자신의 대표자이면 그대로 반환
        }
        // 경로 압축: x의 부모를 재귀적으로 찾아, 루트에 바로 연결되도록 함
        return this.parent[x] = this.find(this.parent[x]);
    }

    // 두 집합을 하나로 합치는 함수
    union(x, y) {
        const rootX = this.find(x); // x의 대표자를 찾음
        const rootY = this.find(y); // y의 대표자를 찾음
        if (rootX !== rootY) {
            this.parent[rootX] = rootY; // 두 집합을 합침 (y를 x에 연결)
        }
    }
}

function solution(G, P, planes) {
    const uf = new UnionFind(G); // G개의 게이트를 가진 Union-Find 생성
    let count = 0; // 도킹된 비행기 수를 카운트

    for (let i = 0; i < P; i++) {
        const gate = planes[i]; // i번째 비행기의 가능한 게이트 번호
        const availableGate = uf.find(gate); // 도킹 가능한 가장 큰 번호의 게이트 찾기

        if (availableGate === 0) break; // 더 이상 도킹할 수 있는 게이트가 없으면 중지

        uf.union(availableGate, availableGate - 1); // 도킹하고 다음 작은 번호로 업데이트
        count++; // 도킹된 비행기 수 증가
    }

    return count; // 최대 도킹 가능한 비행기 수 반환
}

// 입력 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const G = parseInt(input[0], 10); // 게이트의 수
const P = parseInt(input[1], 10); // 비행기의 수
const planes = input.slice(2).map(Number); // 각 비행기의 게이트 번호 목록

console.log(solution(G, P, planes)); // 결과 출력