10775: 공항

풀이 시간

• 40m

구현 방식

• find-union을 이용하여 풀었다

• "공항에는 P개의 비행기가 순서대로 도착할 에정이며, 당신은 i번째 비행기를 1번부터 gi번째 게이트 중 하나에 영구적으로 도킹하려 한다."
  -> parent를 gate들 간의 관계를 나타낼 수 있도록 설정해줘야한다

• 예제 2에서 처음 parent의 상태는 {1:1, 2:2, 3:3, 4:4, 5:5, 6:6}이다.
  
  1) g가 2라면, 일단 2번 게이트에 비행기를 연결시켜주고, 2의 parent를 2-1로 설정해준다. -> {1:1, 2:1, 3:3, 4:4, 5:5, 6:6}
  
  2) g가 다시 2라면, 2번 게이트의 parent 게이트인 1번 게이트에 비행기를 연결시켜주고, 1의 parent를 1-1로 설정해준다. -> {1:0, 2:1, 3:3, 4:4, 5:5, 6:6}
  
  3) g가 3이라면, 3번 게이트에 비행기를 연결시켜주고, 3의 parent를 3-1로 설정해준다. -> {1:0, 2:1, 3:2, 4:4, 5:5, 6:6}
  
  4) g가 다시 3이라면, 3번 게이트의 parent 게이트인 2번 게이트의 parent 게이트인 1번 게이트의 parent 게이트인 0번 게이트에 비행기를 연결시켜주면 되는데, 0번 게이트는 존재하지 않는 게이트이므로 break

코드

import sys

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a); b = find(b)
    #더 작은 노드에 합침
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

G = int(sys.stdin.readline()[:-1])
P = int(sys.stdin.readline()[:-1])


parent = {i: i for i in range(G+1)}

count = 0
for p in range(1, P+1):
    g = int(sys.stdin.readline()[:-1])
    g = find(g) #g의 루트 부모 노드를 찾음

    if g == 0: break # 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

    union(g, g-1)
    count += 1
print(count)

결과