[Python] G2_10775_공항 🛬

https://www.acmicpc.net/problem/10775

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제

---

코드

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

# 도킹 가능한 게이트를 찾는 함수
def find(n):
    # 처음 사용되는 게이트인 경우
    if root[n] == n:
        return n
    root[n] = find(root[n]) # 게이트를 계속 작은 숫자로 바꿔줌
    return root[n]

G = int(input())
P = int(input())
# 게이트 정보를 저장
root = [i for i in range(G+1)]
# 비행기 정보를 저장
plane = [int(input()) for _ in range(P)]

# 최대로 도킹 가능한 비행기 수를 찾아줌
res = 0
for p in plane:
    # 이용가능한 게이트를 찾아줌
    gate = find(p)
    # 더 이상 이용가능한 게이트가 없으므로 폐쇄
    if gate == 0:
        break
    # 비행기 한 대를 댔으므로 -1
    root[gate] -= 1
    res += 1
    
print(res)

Point! 💡

1. 본인이 루트 노드라면, 이는 곧 해당 게이트를 한 번도 사용하지 않았음을 말한다.

2. 만약 루트 노드가 아니라면 사용한 적이 있는 게이트이며, 가리키고 있는 루트 노드가 곧 대안 게이트가 된다.

3. 대안 게이트까지 하나도 존재하지 않아, 루트 노드가 0이 된다면 이는 공항이 폐쇄됨을 의미하여 종료해준다.

게이트 선택 기준 👨‍🏫

2의 plane에게는 1,2이라는 게이트에 도킹할 수 있는 선택지가 주어진다.

• 여기서 우선적으로 본인과 동일한 숫자의 게이트를 선택한다. 없다면 최대한 가까운 숫자의 게이트를 선택한다.

• 만약 다음번에 2이라는 plane이 동일하게 나온다면, 2번 게이트는 이미 사용중이기에 그 이전 숫자인 1번 게이트를 사용하게 된다.

예시 2번을 통한 설명 👨‍💻

초기 root 상태는 다음과 같다. 이는 곧 모든 게이트를 사용할 수 있음을 의미한다.

• root : [0,1,2,3,4]

이제 첫번째로, plane의 원소인 2를 인자로 find 함수를 실행시킨다.

• 현재 root[2] 또한 2이기 때문에, gate에는 2가 그대로 들어가게 된다.

• 여기서 본인과 가장 가까운 숫자인 2번 게이트를 선택해주고, root[2]의 원소를 -1해준다.

• 현 root 상태: [0,1,1,3,4]

두번째로, 동일하게 2라는 원소를 인자로 find 함수를 실행시킨다.

• 이전 과정을 통해서 root[2]에는 2가 아닌 1이 들어있기 때문에, 최종적으로 1을 리턴한다.

• 1번 게이트를 사용할 수 있으므로, 비행기를 도킹하고 root[1]을 -1해준다.

• 현 root 상태: [0,0,1,3,4]

세번째로, 3이라는 원소를 인자로 find 함수를 실행시킨다.

• 현재 root[3] 또한 3이기 때문에, gate에는 3이 그대로 들어가게 된다.

• 3번 게이트를 사용할 수 있으므로, 비행기를 도킹하고 root[1]을 -1해준다.

• 현 root 상태: [0,0,1,2,4]

네번째로, 동일하게 3이라는 원소를 인자로 find 함수를 실행시킨다.

• 이전 과정을 통해서 root[3]에는 3이 아닌 2가 들어있다.

• 다음으로 root[2]에는 1이 들어있으며, root[1]에는 0이 들어있어 최종적으로 0을 리턴한다.

• gate == 0 이기 때문에, 더 이상 이용가능한 게이트가 없는 것으로 판단하고 폐쇄한다.

총 3개의 비행기가 도킹에 성공하였으므로 이를 출력해준다.

---

느낀 점 & 배운 점

1. 오랜만에 유니온 파인드를 사용하는 문제여서 조금 당황했다. 이런 식으로 그리디와 유니온 파인드를 결합할 수 있음을 알게 된 문제였다.

2. 루트 노드를 게이트 번호로 두고, 사용하면 하나씩 줄이며 대안 게이트를 가리키도록 한다는 점을 떠올리기는 쉽지 않았다..