10775번 공항

문제

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

접근 방식

아직 유니온 파인드를 많이 안 풀어봐서 그런지 이렇게 활용될수도 있구나 신기했던 문제..

그리디 아이디어가 가미된 유니온 파인드 방식이다.

유니온 파인드에서 각 노드의 부모는 제일 작은 숫자를 가진다는 특징이 있는데, 이를 활용하여 1 ~ gi 중 도킹되지 않은 가장 큰 게이트(=그리디 아이디어)에 도킹할 수 있다.

코드

G = int(input())  # 게이트 수
P = int(input())  # 뱅기 수

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

planes = []
for _ in range(P):
    planes.append(int(input()))


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


cnt = 0
for plane in planes:
    p = find_parent(plane)
    if p == 0:
        break
    parent[p] = parent[p - 1]  # union
    cnt += 1

print(cnt)