[Python] 백준 / gold / 10775 : 공항

문제 링크 : https://www.acmicpc.net/problem/10775

Union-Find 문제를 연습해봤다. 문제만 읽어서는 Union-Find 문제인지 한번에 알아차리기 힘들었다. 비행기가 들어올 때마다 gi 라는 값을 가지고 들어오는데, gi 이하의 게이트가 남아있어야만 이 비행기는 도킹이 가능하다.

그리디적인 풀이법을 생각할 수 있었는데, 예를 들어 gi = 4 인 비행기가 들어온다면, 4 이하의 게이트 중 가장 큰 값에 도킹시키고 보는 거다. gi = 4 인 비행기가 연속으로 두 대가 들어온다면 Gate 4, Gate 3 순으로 도킹시키면 된다.

나이브하게 생각하면 gi = k 인 비행기가 들어왔을 때, k 이하 가능한 값의 게이트를 k-1, k-2, ... 순차탐색을 해서 도킹할 게이트 자리를 찾아가면 된다. 하지만 조건에서 비행기의 수 G = 10^5 이기 때문에, 시간초과가 나게된다.

이 문제의 알고리즘 분류가 Union-Find인 이유가 여기서 등장한다. 도킹할 자리를 찾아가는 알고리즘을 어떻게 효율적으로 작성할 것인가.

도킹 할 때마다 Union 연산을 수행하면 된다. 예를들어, gi = 4 인 비행기가 Gate 4에 도킹했다고 쳐보자. 그러면 Gate 4 와 Gate 3을 Union 해버리는 것이다. 그러면 다음에 gi = 4 인 비행기가 들어왔을 때 4가 속한 집합의 Root Node 인 3의 자리에 찾아가서 도킹하면 된다. 그리고 또 Gate 2 를 Union 한다.

2가지 기억할 것
1. Union-Find 로 탐색 효율을 높일 수 있다.
2. 순차 탐색 때문에 효율성이 낮다면, 매 처리하는 시점마다 작업을 해주면 효율성을 높일 수 있다.

파이썬 코드

import sys
G = int(sys.stdin.readline())
P = int(sys.stdin.readline())

plane = []
for _ in range(P):
    plane.append(int(sys.stdin.readline()))

parent = [x for x in range(G+1)]


def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]


def union(a, b):
    pa = find(a)
    pb = find(b)
    parent[max(pa, pb)] = min(pa, pb)


answer = 0
for p in plane:
    pp = find(p)
    if pp == 0:
        break
    union(pp, pp - 1)
    answer += 1

print(answer)