[BOJ][Python] 백준 10775번: 공항

1일 1PS 44일차!

📚 문제

---

골드 2

• Find-Union

💡 풀이 과정

---

• 예제 입력 1 에 대해서 살펴보자.
  • 처음 게이트를 [1, 2, 3, 4] 로 초기화 한다.
  • 해당 숫자들은 각 index 로 접근했을 때 도킹할 수 있는 최대 숫자의 게이트를 나타낸다.
  • 입력 4
    • 4 가 들어오면 4번 게이트에 비행기가 들어오기 때문에 이제 도킹이 불가능하며 가능한 게이트 중 가장 큰 수는 3 이다.
    • [1, 2, 3, 3] 으로 업데이트 해야한다.
  • 입력 1
    • 1이 들어오면 위와 같이 진행하고 [0, 2, 3, 3] 으로 업데이트한다.
  • 입력 1
    • 1이 들어왔을 때 리스트의 값이 0 이므로 break 한다.

• 예제 입력 2

  • 처음 게이트를 역시 [1, 2, 3, 4] 로 초기화한다.
  • 입력 2
    • [1, 1, 3, 4]
  • 입력 2
    • [0, 0, 3, 4]
  • 입력 3
    • [0, 0, 0, 4]
  • 입력 3
    • 3번째 리스트 값이 0이므로 break 한다.
• 이때 가능한 가장 큰 게이트를 업데이트하기위해 Union-Find 를 사용한다.
  • 쉽게 생각해서 현재 n 게이트에 비행기가 들어온다면 n 번은 n - 1 번 리스트를 그대로 업데이트하면 된다. n 번은 사용되었고 n - 1 에는 n - 1 보다 작은 게이트 중 사용 가능한 가장 큰 게이트를 나타내기 때문이다.

📌포인트

---

• 시간초과
  • PyPy3 가 더 빠르다는 것을 알고 있기에 해당 언어로 실행하자 통과되었다.
  • 같은 코드를 Python 으로 돌리면 여전히 시간 초과가 발생한다.
• find(x)
  • return find(gates[x]) 로 실행했더니 시간초과가 발생한다.
  • gates[x] = find(gates[x]) 가 단순 find 를 리턴한느 것이 아니라 경로 압축을 진행하는 것이기 때문이다.

💻 코드

---

def find(x):
    if gates[x] == x:
        return x
    gates[x] = find(gates[x])
    return gates[x]


def union(x, y):
    gates[find(y)] = find(x)


G = int(input())
P = int(input())
planes = [int(input()) for _ in range(P)]
global gates
gates = [i for i in range(G + 1)]
cnt = 0

for plane in planes:
    parent = find(plane)
    if parent == 0:
        break
    union(parent - 1, parent)
    cnt += 1

print(cnt)