[백준] 10775번 - 공항 (파이썬)

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

# 공항


def find_parent(x):
    if x != parent[x]:
        parent[x] = find_parent(parent[x])
    return parent[x]


def union_parent(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


G = int(input())
P = int(input())

parent = [i for i in range(G+1)]
plane = []
for _ in range(P):
    plane.append(int(input()))

count = 0
for p in plane:
    x = find_parent(p)
    if x == 0:
        break
    union_parent(x, x-1)
    count += 1

print(count)

 

그리디, Union-Find

1. 비행기가 도착하는 순서를 plane리스트에 기록

2. plane리스트를 앞에서부터 차례대로

    - 해당 비행기의 부모(도킹할 게이트)를 찾는다 : find_parent

    - 부모(도킹할 게이트)가 0 이면, 이후의 비행기 또한 모두 도킹할 수 없음 break

    - 0이 아니면, 이전게이트와 도킹할 게이트를 연결 : union_parent

3. union_parent를 한 횟수 출력

 

union_parent를 적용할 때 약간의 어려움이 있었다.

union-find를 이용해서 게이트가 현재 도킹 되어 있는지를 관리한다.

n번 비행기는 1~n번 게이트에 도킹할 수 있으므로 n번 게이트먼저 도킹 한다. (그리디)

x와 x-1을 해주는 이유는 그리디 알골리즘을 적용하기 위함이다.

find_parent를 해서 나온 결과값은 현재 사용할 수 있는 게이트와 같다.