[python] 백준 10775 공항

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

10775번: 공항

 

문제 해결

•  i번째 숫자 p인 비행기를 주차할 때 p부터 1까지 주차 가능한 지역을 살펴봐서 가능하면 주차하고 모두 안되면 지금까지 주차한 비행기 대수를 구하면 된다.
•  하지만 비행기 대수와 게이트 숫자가 매우 클 수 있다. $10^{5}$ 이므로 두번 풀로 for문을 돌릴 수 없다는 것이다.
•  그러면 한번에 찾을 수 있는 방법을 찾아야한다.
•  이 때 이용되는 것이 Union find이다. i구역 주차가 불가능 하면 주차 가능한 지역을 parents로 두어 parents에 주차하도록 한다.
•  parents에 주차를 하면 parents는 parents-1부터 1까지 주차 가능 지역을 찾아서 그 곳으로 가라고 연결을 시키면 된다.
•  그러면 모든 수를 다 돌리지 않고 빨리 주차할 곳을 알 수 있다.
•  주차할 곳이 없으면 부모가 0이 된다. 그러면 지금까지 주차한 대수를 출력하고 끝내면 된다.

 

CODE

import sys
input = sys.stdin.readline
g= int(input()) # 게이트 숫자
plane = []
num = int(input()) # 비행기 숫자
for _ in range(num):
    plane.append(int(input()))
A = [i for i in range(g+1)] # 주차 경로 알려주기 A[i]=i이면 주차 가능, A[i] = v (0<v<i)이면 v로 가서 주차하라는 뜻

def find_root(x):
    stack = [x]
    while True:
        p = A[x] #A[x]에 parking
        if p == x: #자기자신에 들어갈 수 있으면(i비행기 i에 parking)
            break
        else:
            stack.append(p) # 부모노드로
            x = A[p] # 부모찾기
    while stack:
        temp = stack.pop()
        A[temp] = p
    return p


def union(root):
    next_root = find_root(root-1)
    A[root] = next_root # root에 주차 못하니 next_root로 가시오.

cnt = 0
for i in range(num):
    x = plane[i] # 비행기 num
    root = find_root(x) # 주차 가능한 루트 찾기

    if root ==0: # 주차 가능 구역이 없으면 종료
        break
    union(root) # root는 주차가 되었으니 root-1부터 주차 할 수 있는 비어있는 주차구역을 찾아야 한다.
    cnt += 1
print(cnt)