🏫 공항 (Class 5++)

👉🏻 10775번: 공항

import sys; input=sys.stdin.readline

gates = int(input())
N = int(input())
airplanes = [int(input()) for _ in range(N)]
parent = list(range(gates+1))

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

def union(x, y):
    x = find(x)
    y = find(y)
    
    if x != y:
        parent[x] = y

cnt = 0

for i in range(N):
    gate = find(airplanes[i])
    if gate == 0:
        break
    union(gate, gate-1)
    cnt += 1

print(cnt)

 

---

✨ 왜 이렇게 풀었을까?

💡 초기 설정

• 관련 변수들은 총 4개!
  • gates는 공항에 있는 게이트의 총 개수
  • N은 도착하는 항공기의 수
  • airplanes은 각 항공기가 도착할 때 사용할 수 있는 최대 게이트 번호를 의미합니다.

• 이 중에서 아주 특별하게 사용되는 parent가 있는데, 이 친구는
  
  • 예를 들어, 게이트가 4개면, parent = [0, 1, 2, 3, 4]로 설정되고,
  • 여기서 인덱스는 게이트 번호를 나타내며, 처음에는 모든 게이트가 자기 자신을 가리키게 해서, 해당 게이트가 사용 가능한 상태임을 알려주는 역할을 합니다.

 

💡 find 함수로 현재 사용 가능한 게이트 찾기

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

• 이 find 함수는 union-find 알고리즘에서 기본적인 함수죠!
• 주어진 게이트 번호 x에서부터 시작해서, 아직 사용 가능한(자기 자신을 가리키는) 게이트를 찾아주는 역할을 수행합니다.
  1. 만약 parent[x]가 x와 같다면, 그 게이트는 아직 사용 중이 아니므로 바로 반환해줍니다.
  2. 만약 아니라면, 재귀 호출을 통해 더 낮은 번호의 사용 가능한 게이트(대체 게이트)를 찾습니다. (이 부분이 가장 중요!!)
  3. 재귀 호출 후에는 중간에 거쳤던 모든 게이트의 부모를, 바로 찾은 대표 게이트로 업데이트하여 다음 검색 시에는 더 빠르게 찾을 수 있도록 해줍니다.

 

💡 union 함수로 게이트 사용 처리하기

def union(x, y):
    x = find(x)
    y = find(y)
    
    if x != y:
        parent[x] = y

• 사용한 게이트 x를 사용 처리하기 위해서, 게이트의 대표를 바로 아래 번호의 게이트 y로 변경해줍니다.
  1. 예를 들어, 항공기가 게이트 4에 도착했다고 가정하면, find(4)는 4를 반환하고,
  2. 항공기가 게이트 4를 사용하게 되면, union(4, 3)을 호출해서 게이트 4의 대표를 게이트 3으로 바꿉니다.
  3. 이렇게 해서 다음에 게이트 4를 찾으려고 하면, find 함수가 게이트 3을 반환하게 되어, 이미 사용된 게이트를 건너뛰게 되는 구조입니다.