[Graph] 이코테 “탑승구” Python 풀이

문제

• 공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.
• 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 영구적으로 도킹해야 합니다.
• 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.
• 또한 P개의 비행기를 순서대로 도킹하다가, 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다.
• 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다.
• 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

입력 조건

• 첫째 줄에는 탑승구의 수 G (1 <= G <= 100,000)가 주어집니다.
• 둘째 줄에는 비행기의 수 P (1 <= P <= 100,000)가 주어집니다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi (1 <= gi <= G)가 주어집니다.
• 이는 i번째 비행기가 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

출력 조건

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

입력 예시

4
3
4
1
1

4
6
2
2
3
3
4
4

출력 예시

2

3

풀이

• 중요 부분
  • 공항에는 P개의 비행기가 차례대로 도착할 예정이며,
  • i번째 비행기를, 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 영구적으로 도킹해야 한다.
• 이 문제는 서로소 집합 알고리즘을 이용하면 효율적으로 해결할 수 있다.
• 비행기가 순서대로 들어오면, 차례대로 도킹을 수행해야 하는데,
• 도킹을 수행할 때, 가능한 큰 번호의 탑승구로 도킹을 수행한다고 가정하며,
• 가능한 큰 번호의 탑승구의 루트 노드와 루트 노드의 왼쪽 노드를 합집합 연산한다.
• 이때 도킹 가능한 가장 큰 번호의 루트 노드가 0이라면, 더 이상 도킹이 불가능한 것으로 판단한다.
• 해당 알고리즘은 그림을 그려가며 이해하는게 쉽다.
• 알고리즘의 세부 설명은 아래 예제 코드와 같다.

예제 코드

import sys

# 특정 원소가 속한 집합을 찾기
def find(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 탑승구의 수
g = int(sys.stdin.readline())

# 비행기의 수
p = int(sys.stdin.readline())

# 부모 테이블 초기화
parent = [i for i in range(g+1)]

# 도킹할 수 있는 비행기의 최대 개수
result = 0

for _ in range(p):

    # 비행기가 도킹할 수 있는 탑승구의 가장 큰 번호
    docking = int(sys.stdin.readline())

    # 해당 탑승구의 루트 노드
    root = find(parent, docking)

    # 루트 노드가 0이라면
    if (root == 0):
        break
    # 루트 노드가 0이 아니라면
    else:
        # 루트 노드와 루트 노드의 왼쪽 노드를 합집합
        union(parent, root, root-1)
        result += 1

print(result)

참고

• 이것이 취업을 위한 코딩 테스트다. with python