[BOJ 10775, Python 3] 공항

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

10775번: 공항

 

풀이

그리디도 비슷한 유형의 문제들이 많이 보이네요.

일단 1번부터 g[i]번 게이트까지 영구적으로 도킹하려고 하면, 도킹할 수 있는 게이트의 최댓값을 찾아서 도킹해주는 것이 최적임을 알 수 있습니다. g[i]번부터 시작하여 1번까지 확인해보면서 도킹할 수 있는 곳에 도킹한다는 말입니다.

왜냐하면 만약 1~4번 게이트까지 도킹하는 비행기를 1번에 도킹하고, 1번 게이트만 도킹할 수 있는 비행기를 도킹하려고 하면 답은 2이지만, 1로 끝나기 때문입니다. 이렇게 g[i]번부터 확인해보면서 도킹할 수 있는 곳을 찾아가는 것이 최적해입니다.

 

하지만 g[i]번부터 1번게이트까지 확인하려면 G의 최댓값이 100,000이라서 비행기 한 개씩 g[i]번부터 1번부터 확인하는 O(N^2)풀이를 사용할 수 없습니다.

이때 O(N^2)과 똑같이 작동하면서 시간이 더 빠른 분리집합 / 유니온파인드 기법을 사용합니다.

부모 노드는 게이트 번호 자기 자신으로 설정하고, 합칠 때는 현재 도킹한 번호의 부모 노드를 [(현재 도킹한 번호 - 1)의 부모 노드]로  설정해주면 됩니다.

 

왜 이렇게 하냐면 만약 4, 2, 4, 4라는 입력값이 들어왔다고 해봅시다.

그러면 첫 번째는 find(4) = 4로 4번 게이트에 도킹을 했으니, merge(4, 3)을 통해 parent[4] = 3으로 바꿉니다.

두 번째 비행기도 도킹을 해야하는데 find(2) = 2로 나왔으니 2번 게이트에 도킹합니다. 그다음 merge(2, 1)를 하여 parent[2] =1로 바꿉니다

세 번째도 도킹을 할 때 find(4)를 하면 3이 나오니 3번에 도킹합니다. 그 후 merge(3, 2)를 하는데 parent[2] = 1이므로 parent[3] = 1로 설정됩니다.

마지막으로 4번이 들어오면 find(4) => 3 => parent[3] => 1로 1번 게이트에 도킹합니다. 그 후 merge(1, 0)을 해서 parent[2] = 1로 설정됩니다.

 

이후에 또 4이하의 값을 가진 비행기가 들어오면 find(x)를 할 때 0이 나오므로 더 이상 도킹을 할 수 없어서 종료하고 답을 출력하게 됩니다.

 

유니온 파인드로 이렇게 할 수 있다니 신기하네요.

 

코드

def find(x):
    if x == parent[x]: return x
    parent[x] = find(parent[x])
    return parent[x]
 
def merge(x, y):
    x = find(x)
    y = find(y)
    parent[x] = y
 
input = __import__('sys').stdin.readline
g = int(input())
p = int(input())
parent = [i for i in range(g+1)]
airplane = [int(input()) for _ in range(p)]
ans = 0
for x in airplane:
    val = find(x)
    if val > 0:
        ans += 1
        merge(val, val-1)
    else: break
print(ans)