[백준 10775번] 공항 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

def findparent(x):
  if parent[x] == 0:
    return False
  if gate[parent[x]] == 0:
    return parent[x]
  parent[x] = findparent(parent[x])
  return parent[x]

G = int(input())
P = int(input())

gate = [0]*(G+1)
parent = {i:i-1 for i in range(1,G+1)}
result = 0
fail = False
for i in range(P):
  g = int(input())
  if fail:
    continue
  if gate[g] == 0:
    gate[g] = 1
    result += 1
  else:
    if findparent(g):
      gate[findparent(g)] = 1
      result += 1
    else:
      fail = True

print(result)

 

시간을 생각하지 않으면 그냥 이중for문 돌리면 되지만 그러면 시간초과가 나는 문제이다.

union-find 알고리즘을 통해서 해결하였다.

모든 게이트번호에 대해서 부모를 번호-1한 값으로 설정하고, 만약 게이트가 이미 차있으면 부모를 찾고, 경로압축을 하는 방식으로 시간초과를 해결하였다.

 

 

오늘의 교훈) union-find 알고리즘은 유용하다!