[BOJ 10775] 공항 (Python)

박지훈·2021년 4월 11일
0

문제

링크



풀이

처음에는 비행기를 중심으로 1번 ~ 입력받는 gi번 사이의 모든 게이트를 탐색하여 그중 비어있는 게이트에 비행기를 도킹시키려고 하였다. 시간복잡도는 O(GP)100,000 x 100,000 = 10,000,000,000 시간초과를 예상하였고, 다른 방법으로 풀려하였다.

하지만, 방법이 생각이 나지않았고 다른 사람의 풀이를 참고하여 union-find 알고리즘을 사용한다는 것을 알게 되었다. (시간복잡도 훨씬 낮춰줌) (원래 union-find 알고리즘은 알고 있었으나 왜 이 문제에 사용해야 하는건지는 몰랐다. 반성해야겠다...)

참고 : 다른 사람의 풀이

비행기를 도킹할 때 항상 도킹할 수 있는 가장 큰 수의 게이트에 도킹해야한다. 왜냐하면 최대 도킹 수를 구해야하기 때문이다. 예를 들어

(Ex)

만약 1번 비행기를 Gate 1에 도킹한다면, 2번 비행기는 어느 게이트에도 도킹할 수 없다. 최대 1대만 도킹이 가능하다.

그러나, 1번 비행기를 Gate 2에 도킹하면, 2번 비행기는 1번 게이트에 도킹이 가능하여 최대 2대를 도킹시킬 수 있다. (최댓값)



문제에서 주어진 첫 번째 예제 입력을 통해 간단하게 설명하려한다. 이해가 가지 않는다면 위 참고 링크에 들어가면 확실하게 이해할 수 있을 것이다.

(Ex)

위 그림을 보면 Gate 3과 Gate 4를 연결하였다. 이 의미(parents[4] = 3)는 Gate 4번은 도킹되어있어서 다른 비행기가 도킹 못한다고 생각하면 된다.
주어진 예제 입력과 다르게 만약 바로 다음 Airplane의 입력이 4라면, Gate 4는 도킹되어 있으므로 Gate 3에 도킹해야한다. (최대 도킹 수를 구하려면 도킹할 수 있는 남은 게이트 중 가장 큰 수의 게이트에 먼저 도킹해야함.) 여기서 Gate 3은 도킹된 비행기가 없으므로 (parents[3] = 3) 도킹이 가능하다.
즉, parents[x] == x이면 x번 게이트에 도킹할 수 있다는 얘기이다. 단, x=0은 제외다.
parents[x] != x이면 x번 게이트에 도킹할 수 없으므로 1번 ~ (x-1)번의 게이트 중 비어있는 게이트를 찾아야한다. 왼쪽 옆 게이트를 확인하면 된다.
parents[x] = 0이면 비행기가 어느 게이트에도 도킹할 수 없어 공항이 폐쇄되고, 어떤 비행기도 도착할 수 없게되어 종료된다. (노드 0번(Gate 0번)을 생성한 이유이다.)

이러한 방법으로 도킹 표시를 하여 문제를 풀면 된다.



코드

import sys

# 비행기를 도킹할 때 항상 넣을 수 있는 가장 큰 수의 게이트에 도킹해야함. (최대 도킹 수를 구해야하므로)
input = sys.stdin.readline
G = int(input())
P = int(input())
docking = list(int(input()) for _ in range(P))
parents = [i for i in range(G + 1)]
ans = 0


def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]  # 경로압축


def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)

    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB


for d in docking:
    root = find(parents, d)
    # 0일 때 끝나는 이유 -> 비행기가 어느 게이트에도 도킹할 수 없으면 공항 폐쇄되고,
    # 이후 어떤 비행기도 도착할 수 없기 때문에 더이상 탐색할 필요가 X
    if root == 0:
        break

    # union(parents, d, d - 1) --> (Ex) 2-3 연결되어있고 1은 비어있음. d=3이면 1-2-3 연결되어야 하는데
    # 3의 부모인 2와 1을 연결해야하는데, 위 코드는 3과 2를 연결해서 오류발생!
    union(parents, root, root - 1)
    ans += 1

print(ans)

profile
Computer Science!!

0개의 댓글