[백준] 10775 공항 공항 - 파이썬 Union-find

10775번: 공항

 

문제 접근 방법

가장 먼저 시도 했던 풀이 -> 시간초과

도킹 리스트를 O(N) 순회하고 다시 비어 있는 게이트를 찾기 위해 항상 이중 반복문이 되어 버려 시간 초과가 발생한 것 같다.

import sys
input = sys.stdin.readline

G = int(input())
D = int(input())
dock_p = [int(input()) for _ in range(1, D+1)]  # 도킹 리스트
gates = (G + 1) * [0] # 실제 게이트수보다 +1
for p in dock_p:
  if gates[0] == 1: # 0번째 게이트가 1이면 종료
    break
  else:
    if gates[p] == 0: # 게이트가 비어있으면
      gates[p] = 1 # 도킹
    else: # 게이트가 비어있지 않다면
      while True: # 순회를 돈다.
        if gates[p-1] == 0: # -1의 게이트가 비어 있으면
          gates[p-1] = 1 # -1 게이트에 도킹
          break
        else: # 차있다면 
          p = p-1 
          continue # -2 도킹 순회를 시작한다.
 print(sum(gates[1:]))

 

최종 제출코드

Union-find라는 알고리즘을 인터넷에 찾아볼 수 있었다. 재귀를 통해 O(1)으로 시간 단축을 할 수 있도록 경로 단축이 되었다. 해당 과정은 https://gaza-anywhere-coding.tistory.com/69 블로그를 참고했다. 

 

import sys
input = sys.stdin.readline
G = int(input())
D = int(input())
dock_p = [int(input()) for _ in range(1, D+1)]
parent = {i:i for i in range(G+1)}

def parent_find(x):
  if x == parent[x]:
    return x
  p = parent_find(parent[x])
  parent[x] = p
  return parent[x]

def union(x, y):
  x = parent_find(x)
  y = parent_find(y)
  parent[x] = y

cnt = 0
for i in dock_p:
  x = parent_find(i)
  if x == 0:
    break
  union(x, x-1)
  cnt +=1
print(cnt)