[baekjoon] 백준 10775번(파이썬): 공항

문제

10775번: 공항

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

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

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

- 공항에는 P개의 비행기가 순서대로 도착할 예정이다.

- 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려 한다.

- 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

- 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어 한다.

- 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는지를 구하는 문제이다.

- 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

- 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

-  비행기의 순번대로 g (1 ≤ g ≤ G) 가 주어진다.

알고리즘

- union-find 알고리즘으로 풀어야 한다.

- find() 함수를 만든다. find() 함수는 비행기 번호로 부모 테이블을 구하는 함수이다. 여기서 부모 테이블은 쉽게 생각해 비행기가 도킹 가능한 곳이다.

- union() 함수를 만든다. union() 함수는 해당 부모 테이블을 -1 해주어 앞에 있는 부모 테이블과 연결해주는 것이다. 부모 테이블이 0이 되면 그 게이트는 도킹할 수 없다. 

- 게이트 수를 입력받는다.

- 비행기의 수를 입력받는다.

- 비행기의 순번대로 gi를 입력받는다.

- 부모 테이블을 순서대로 초기화한다.

- 반복문을 통해 비행기를 도킹한다.

- 현재 비행기가 도킹할 게이트가 없어 도킹할 수 없으면 멈춰준다.

- 게이트로 도킹을 하면 도킹 횟수를 카운트해주고 현재 번호 비행기의 부모 테이블을 -1 해준다. 

코드

import sys


# 부모 테이블 찾기
def find(x):
    # 비행기 번호와 부모 테이블 번호가 같으면 비행기 번호 리턴
    if parent[x] == x:
        return x
    # 재귀적으로 부모 테이블을 찾는다.
    # 부모 테이블 리턴
    parent[x] = find(parent[x])
    return parent[x]


# 부모 테이블 바꾸기
def union(a, b):
    a = find(a)
    b = find(b)
    # 부모 테이블을 -1 해준 값으로 바꿔 앞에 부모 테이블과 연결한다.
    parent[b] = a


G = int(sys.stdin.readline())
p = int(sys.stdin.readline())
g = [int(sys.stdin.readline()) for x in range(p)]

# 부모 테이블 초기화
parent = [i for i in range(G + 1)]
# 도킹 횟수
cnt = 0

for i in g:
    # 현재 도킹하려는 게이트
    docking = find(i)

    # 도킹할 곳이 없으므로 멈춘다.
    if docking == 0:
        break

    # 도킹 횟수 카운트
    cnt += 1
    # 현재 번호 비행기가 도킹을 했으므로 -1을 해준다.
    union(docking - 1, docking)
    print(parent)

print(cnt)

결과

 위 코드에서 밑에 for문에 바로 앞에 print(parent)를 작성하게 되면 union-find 알고리즘을 다음 출력화면과 같이 쉽게 확인할 수 있다.

<출력 화면>

 위 출력화면을 보게 되면 처음에 parent(부모 테이블)이 순서대로 초기화되어있는 것을 확인할 수 있다. 그리고 find() 함수로 들어가게 되고 find() 함수에서 비행기 번호와 부모 테이블이 번호가 같은지 확인한다. 이때 같으면 바로 도킹시킬 수 있기 때문에 비행기 번호를 리턴 받는다. 도킹을 했으므로 도킹 횟수를 카운트하고 4번 비행기의 부모 테이블인 4는 -1을 해주어 3번 부모 테이블과 연결시킨다. 이유는 4번 비행기의 부모를 3번 테이블로 바꿔줌으로써 4번 게이트로는 도킹을 할 수 없게 되는 것이다. 다음으로 1번 비행기와 1번 부모 테이블을 비교하고 번호가 같으므로 바로 도킹을 시켜 비행기 번호를 리턴 받는다.  다시 도킹을 했으므로 도킹 횟수를 카운트하고 1번 비행기의 부모 테이블인 1을 -1 해주어 0번 부모 테이블과 연결시킨다. 마지막으로 1번 비행기가 또 도킹을 하러 왔는데 이때 1번 비행기의 부모 테이블은 0 임으로 도킹할 게이트가 없어 반복문을 종료한다. 그리고 이때의 도킹 횟수를 출력하면 된다.

<출력화면>

 위 다른 예시의 출력화면을 보도록 해보자. 처음에 2번 비행기와 2번 부모 테이블을 비교를 한다. 2번 비행기와 2번 부모 테이블의 번호가 같으므로 바로 2번 게이트에 도킹한다. 이때 도킹 횟수를 카운트하고 2번 부모 테이블의 -1을 해주어 1번 비행기의 부모 테이블과 연결시킨다.  그리고 또다시 2번 비행기가 오는데 2번 테이블의 부모 테이블을 find() 함수를 통해 찾게 되면 2번 비행기의 부모 테이블은 1인 것을 확인할 수 있다. 2번 비행기는 1번 게이트의 도킹하고 도킹 횟수를 카운트한다. 2번 비행기의 부모 테이블인 1은 다시 -1을 해주어 0번 부모 테이블과 연결시킨다. 여기서 1번 게이트로는 도킹을 할 수 없게 된다. 다음으로 3번 비행기가 오는데 3번 비행기는 부모 테이블과 번호가 같으므로 바로 도킹을 한다. 다시 도킹 횟수를 카운트하고 3번 부모 테이블 번호를 -1 해주어 2번 부모 테이블과 연결시킨다. 그리고 다시 3번 비행기가 오고 자신의 부모 테이블이 0이기 때문에 도킹할 게이트가 없어 반복문을 종료시킨다. 

따라서 코드를 분석하게 되면 union-find 알고리즘이 왜 쓰이는지와 어떻게 쓰이는지만 알면 쉽게 풀 수 있는 문제였던 것 같다. 

github

junjange/CodingTest