[백준] 공항

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

10775번: 공항

그리디 알고리즘과 분리집합을 이용하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

1~G번 게이트가 있는 공항에 비행기 P대가 옵니다. 이 때, 각 비행기는 숫자 gi를 가지는데 이 1<=k<=gi 인 k번 게이트에만 비행기가 들어올 수 있을 때, 비행기를 최대 몇대까지 도킹시킬 수 있는지를 return하는 문제입니다. 

 

가장 처음에 이 문제를 Greedy로 그냥 해결하려고 시도하였는데 시간초과가 발생했고 이후의 분리집합을 이용하는 과정을 추가하는 순으로 설명해 보려 합니다. 

 

<Solution>

우선 이 문제를 처음 보았을 때 든 생각은 "그러면 매번 gi부터 시작해서 -1씩 하면서 도킹 안된 게이트가 있다면 거기에 도킹을 하면 되지 않는가?" 라는 생각 이었습니다. 

 

한마디로 요약하면 Greedy알고리즘을 사용하자 였습니다. 

4
6
2
2
3
3
4
4

문제에서 주어진 위의 예시 상황을 생각해보면, gi list 집합은 gi = [2,2,3,3,4,4] 이렇게 됩니다. 이 때, 

공항 게이트를 1차원 배열로 표현하면, 

 

[0,0,0,0,0] (가장 왼쪽의 0은 사용하지 않음 & 비행기가 없는 것은 0 있는 것은 1로 표현합니다)

이렇게 됩니다. 

• 1. 가장 처음 2가 주어지므로 1,2 게이트가 모두 비었으므로 더큰 2번 게이트에 비행기를 도킹합니다.
  [0,0,1,0,0]
• 2. 다음으로 2가 주어지는데 2번게이트에는 비행기가 있으므로 다음으로 큰 1번 게이트에 비행기를 도킹합니다.
  [0,1,1,0,0]
• 3. 다음으로 3이 주어지므로 가장 크면서 비행기가 없는 3번 게이트에 비행기를 도킹합니다.
  [0,1,1,1,0]
• 4. 다음으로 3이 주어지는데 3,2,1게이트 순으로 확인했을 때 가능한 게이트가 없으므로 종료합니다.

이러한 과정을 통해 3이라는 결과가 나오게 됩니다. 

이것을 코드로 그대로 구현하면 됩니다. 

(시간초과 풀이)

import sys

G = int(sys.stdin.readline().rstrip())
P = int(sys.stdin.readline().rstrip())

gi_list = [int(sys.stdin.readline().rstrip()) for _ in range(P)]
gate = [0] * (G+1)
count = 0

for gi in gi_list:
    available_flag = 0
    for i in range(gi, 0, -1):
        if gate[i] == 0:
            gate[i] = 1
            available_flag = 1
            break
    
    if available_flag == 1:
        count+=1
    else:
        break
print(count)

 

하지만 이 풀이는 시간초과가 발생하게 됩니다. 

쫌 극한의 testcase를 생각해 봅시다. 매번 gi 보다 작으면서 도킹안된 가장 큰 게이트를 바로 찾지 못하는 경우들일 것입니다. 이것을 통해 최악의 시나리오를 구성해봅시다.

 

<최악의 시나리오>

1. 가장 처음에는 아무것도 도킹되지 않았으므로, 1번의 try 만에 바로 찾을 것입니다. (1번의 try)

2. 2번째에는 조회하니 이미 도킹된 것이 나와서 이후의 것에서 찾습니다. (2번의 try)

3. 3번째에는 조회하니 첫번째, 두번째에서 도킹한 것이 차례로 나와서 세번째 만에 찾습니다. (3번의 try) 

....

이렇게 진행이 되면, 총 P! (P = 비행기의 갯수) 만큼의 try가 필요하게 됩니다. time complexity 측면에서 factorial의 complexity는 거의 최악에 가까우므로 시간 초과가 날 것임을 알 수 있습니다.

 

이 시나리오를 어떻게 고쳐야 할까요? 

간단한 예시로 생각해봅시다. 총 10개의 gate가 있다고 생각해봅시다. 이 중 3,4,5,6번 게이트에는 이미 비행기가 있습니다. 그렇다면 우리는 gi가 5일 때도 5,4,3에 대해 check를 해야하고, gi가 6일 때도 6,5,4,3에 대해 check를 해서 2 또는 1이 비었구나를 알 수 있습니다. 여기에서 5,4,3에 대한 check가 중복해서 일어나는 것을 알 수 있습니다.

 

이 과정을 union find의 경로압축 과정을 통해 줄일 수 있습니다. 한마디로 처음 5,4,3의 searching 과정이 일어날 때, parent를 활용해 사전에 5의 parent가 보니까 3으로 가더라를 기록을 해두면 이후에는 5를 보고 바로 3을 찾을 수 있습니다. 이처럼 경로 압축을 하는 방식으로 코드를 진행시키면 됩니다.

 

경로 압축을 하지 않은 Union Find 알고리즘은

node 수 : V

find 또는 union의 연산 개수 : M

에서 O(VM)의 시간복잡도를 가지는 것으로 알려져 있고, 

 

경로 압축을 하는 경우, 

node 수 : V 

최대 V-1개의 union연산, M개의 find 연산이 가능할 때, 

의 시간복잡도를 가진다고 알려져 있습니다. 

(추후 기회가 되면 포스팅으로 다루어 보도록 하겠습니다.)

 

실제 코드 구현은 아래와 같습니다.

import sys

G = int(sys.stdin.readline().rstrip())
P = int(sys.stdin.readline().rstrip())

gi_list = [int(sys.stdin.readline().rstrip()) for _ in range(P)]
parent = [i for i in range(G+1)]
parent[0] = 0

def find_parent(k):
    if parent[k] == k:
        return k
    parent[k] = find_parent(parent[k])
    return parent[k]

count = 0
for gi in gi_list:
    p = find_parent(gi)
    if p:
        count+=1
        parent[p] = parent[p-1]
    else:
        break

print(count)