[유니온 파인드] Python - 10775번, 공항

www.acmicpc.net/problem/10775

import sys
input = sys.stdin.readline


def findParent(x):
    if parent[x] == x:
        return x

    p = findParent(parent[x])
    parent[x] = p

    return p


def union(x, y):
    x = findParent(x)
    y = findParent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


if __name__ == '__main__':
    G = int(input())
    P = int(input())

    airplanes = [int(input()) for _ in range(P)]
    parent = [i for i in range(G+1)]
    cntDocked = 0

    for airplane in airplanes:
        x = findParent(airplane)

        if x == 0:
            break
        union(x, x-1)
        cntDocked += 1

    print(cntDocked)

유니온 파인드를 모르면 풀 수 없는 문제이다.

 

4
6
2
2
3
3
4
4
3

의 경우이다.

유니온 파인드에서의 한 집합을, 굵은 외각 라인으로 표현하였으며,

비행기가 도킹된 게이트를, 녹색 배경으로 표현하였다.

 

for문으로 비행기가 도킹되기를 원하는 게이트들(airplanes)을 돌면서, 도킹한 게이트를 그 이전 게이트와 Union 처리하고, 카운트(cntDocked)를 증가시킨다. Union 전에, Find 함수를 통해 도킹하고자 하는 게이트(airplane)가 이미 0과 Union 되었다면 즉시 break한다.

 

사실 직관적으로 문제를 푸는 것을 좋아하는 나는, 유니온 파인드라는 것을 이름만 들어본 채로 넘겼었는데, 결국엔 이런 상황이 닥치게 되었다.