[맛있는물회] [파이썬] <백준 알고리즘> [Union-Collapsing Find] 10775번 "공항"

문제 조건

---

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

Input

---

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

 

Output

---

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

생각한 아이디어

---

상당히 시간이 오래걸린 문제이다.

이전 문제에서는 

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

1976번: 여행 가자

단순하게 union-find 만 구현하면 되는 문제여서 쉽게 접근할 수 있었지만,

이번 문제는 단순 union-find로는 시간초과가 발생하는 문제이다.

 

 

단순히 노드의 Parent를 찾기위해서는 

이와 같이 재귀를 사용하거나 while 문으로 단순하게 찾을 수 있다.

하지만 이렇게 되면 인풋값이 많아질때 문제가 발생한다.

 

 

이렇게 트리의 길이가 무한히 길어진다는 것이다.

그렇게 되면 parent node를 찾는 시간이 계속해서 길어진다.

 

 

 

이를 해결하기 위해 사용하는 기법이 Collapsing Find이다.

Find 과정중에 collapsing을 해주면서 트리의 길이를 낮추어 주는 것이다.

 

 

재귀적 성질을 이용하여, root node에서는 자신을 리턴하고, 그것이 아니라면 자신의 parent node를 찾아서 값을 갱신해준다.

이렇게 함으로써 트리의 길이는 짧게 유지가 가능하다.

 

 

 

 

풀이 과정은 parent 배열을 활용한다.

비행기를 도킹하기위해서는 주어진 게이트값에서 큰값부터 하나씩 줄어들어야한다.

만약 주어진 값의 parent가 0 이라면 더 이상 값 이하에서 도킹할 자리가 없다는 것을 의미하기 때문에 Break 하고 출력을 해주면된다.

 

그게 아니라면 parent node의 바로 왼쪽 값의 parent를 구해서 union 해주고 다시 값을 받으면 된다.

 

소스코드

import sys
import math
from collections import deque
import copy
input=sys.stdin.readline
INF=sys.maxsize

def find(parent, n):
   if n==parent[n]: return n
   else:
      #collapsing process
      #이 과정 없이 단순하게 while이나 재귀로 find하면 노드끼리의 길이가 무한정 길어지기 때문에 collapsing으로 트리의 높이를 낮춘다.
      parent[n] = find(parent,parent[n])
      return parent[n]
      
def union(parent,x,y):
   x,y=find(parent,x),find(parent,y)
   parent[x]=y
   
if __name__ == "__main__":
   g=int(input())
   p=int(input())
   arr=[int(input()) for _ in range(p)]
   parent=[i for i in range(0,g+1)]

   cnt=0
   for i in range(0,p):
      tmp=find(parent,arr[i]) 
      if tmp== 0:
         break
      else:
         union(parent,tmp,tmp-1)
         cnt+=1
   print(cnt)

 

*파이썬 문법 정리