[BOJ]10775번: 공항

by

문제

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

10775: 공항

예 1: (2)(?)(?)(1) 형식으로 도킹할 수 있습니다. 세 번째 기체는 도킹할 수 없습니다. 예시 2: (1)(2)(3)(?) 형태로 도킹이 가능하며, 4번째 평면은 절대 도킹이 불가능하여 다른 도킹이 불가능합니다.

www.acmicpc.net

설명

이중 반복으로 해결하려고 했지만 만료되었습니다. 그래서 포기하고 구글링을 하다가 union_find라는 알고리즘을 발견했습니다.

전체 코드

import sys
input = sys.stdin.readline

G = int(input())
P = int(input())
planes = ()
gate = (0,)
for i in range(P):
    planes.append(int(input()))
for i in range(G):
    gate.append(i+1)

cnt = 0

def union_find(parent, x):
    if parent(x) == x:
        return x
    parent(x) = union_find(parent,parent(x))
    return parent(x)

# def union_find(parent, x):
#     if parent(x) == x:
#         return x
#     return union_find(parent,parent(x))


for g in planes:
    plane = union_find(gate, g)
    if plane == 0:
        break
    else:
        cnt+=1
        gate(plane) = gate(plane-1)
    
    
print(cnt)

union_find 함수를 보면 주석이 달린 부분과 주석이 없는 부분이 다르게 동작합니다.