[PS | 한 번에 맞자!] 백준 10775

0. 문제

공항

10775번: 공항

---

1. 문제 생각

공항 도킹에 대한 한국어 풀이가 생각보다 이해가 잘 되지 않아 예제를 계속 읽고서야 이해가 되었다.
차라리 밑에 예제를 예제 2 : [2][1][3][?] 로 풀이 방법을 줬으면 더 이해가 잘 되었을텐데 😥

아무튼 이 문제의 핵심은 

"i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다." 이다.

즉 최대한 gi(가능한 한 뒤에서부터)에서부터 시작하여 게이트에 비행기를 도킹시킨다. 이후 비행기들은 그 전 것들에 도킹될 수 있으므로 union(dest, dest-1)을 시켜 이후 재귀적으로 parent를 할당받을 수 있도록 구현한다.

만약 계속해서 재귀하다가 0을 parent로 갖게 된다면 1~gi 중 어느 게이트에도 도킹될 수 없다는 의미이므로 공항을 폐쇄시켜 break문을 실행한다.

---

2. 문제 구현

import sys
input=sys.stdin.readline

def find(target):
    if target == airport[target] :
        return target
    else:
        airport[target]=find(airport[target])
        return airport[target]

def union(a, b):
    a = find(a) #이거 빼먹지 않도록 주의ㅠㅠㅠ
    b = find(b)
    if a < b: airport[b] = a
    else: airport[a] = b

G=int(input().rstrip()); P=int(input().rstrip())
airport = [port for port in range(G+1)]
ans=0
for i in range(1,P+1): #i는 비행기
    a=int(input())
    dest = find(a)
    if dest == 0 : break
    union(dest, dest-1)
    ans+=1
# print(airport)
print(ans)

 

---

3. 한 번에 풀었는가? X

경로 압축 최적화를 하지 못해 한 번에 풀지 못하였다. union find에서는 아래와 같이 최적화를 하는 것이 좋겠다.!

# 틀린 코드
def find(target):
    if target == airport[target] :
        return target
    return find(airport[target])
    
# 맞은 코드
def find(target):
    if target == airport[target] :
        return target
    else:
        airport[target]=find(airport[target])
        return airport[target]