[백준] 10775번: 공항

문제를 읽고나서 바로 생각나는 풀이법은 단순하게 -1로 초기화 돼있는 gate배열에서 g번째 gate에 도킹하고 싶을 때 gate[g]부터 인덱스를 하나씩 줄여나가면서 비어있는(gate[i] == -1) 자리에 도킹을 하는 것(gate[i] = 0)이었다.

import sys
input = sys.stdin.readline
G = int(input())
P = int(input())
gate = [-1 for _ in range(G+1)]
arr = [int(input()) for _ in range(P)]

ans = 0
for num in arr:
    while num > 0:
        if gate[num] == -1:
            gate[num] = 0
            ans += 1
            break
        num -= 1
    if num == 0:
        break
print(ans)

근데 이렇게 풀면 시간초과가 뜬다🙄 그래서 union-find를 써줘야만 풀린다.
Union find는 수업에서 크루스칼의 알고리즘을 배울 때 cycle check에 써먹었던 것이 기억난다. union-find는 그래프에서 두 노드가 같은 집합에 있는지 판별한다. 문제랑 무슨 상관??

일단 union-find 알고리즘 자체는 재귀적으로 표현이 돼있어서 되게 쉽다. UNION은 두 노드를 같은 집합에 속하게 만드는 함수이고, FIND는 한 노드의 루트노드를 구하는 함수다. 서로 다른 두 노드의 합집합여부를 따질 때는 FIND를 이용해서 비교하면 될 것이다.

UNION(a, b):
	root1 = FIND(a) // a의 루트
	root2 = FIND(b) // b의 루트
	if root1 != root2 // 다르면
		parent[root1] = root2 // 합치기

FIND(curr): 
	if parent[curr] == curr
		return curr
	while parent[curr] != curr
		curr = parent[curr]
	return curr

이 문제에서 중요한 부분은 여기다.

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

이걸 계속 검사해야하기 때문에 그리디 알고리즘에서는 시간초과가 났던 거다. 여기서 유니온 파인드를 사용하면 해결이 된다.

유니온 파인드를 사용한 풀이라고 해서 그리디로 풀었던 원리와 다르진 않은다. 근데 시간복잡도를 생각하면, 그리디는 O(G*P) 이고 유니온 파인드는 O(P)여서 속도차이가 확연하다.

근데 애초에 입력의 개수가 최대일 때를 생각하면, (G = P = 10^5) 역순으로 배열 요소를 하나하나 검사 시 시간초과가 나는 것이 당연하다는 걸 알 수 있었다😥

---

union-find 적용하기

그럼 단순히 모든 게이트를 검사하지 않고 union-find로 게이트 번호를 바로 얻는 방법이 뭘까

gi를 리스트에 입력받은 후 각 요소별로 반복하는데,

0. 도킹 가능한 gate가 없다면 종료
   if find(g) == 0: break
1. 도킹하고자 하는 게이트 find(g)와 이전 게이트를 union
2. find 연산으로 도킹 가능한 gate를 O(1)만에 얻는다

정답 코드

import sys
input = sys.stdin.readline
G = int(input())
P = int(input())
parent = [i for i in range(G+1)] // 자기 자신으로 초기화

def find(curr):
    if parent[curr] == curr:
        return curr
    parent[curr] = find(parent[curr])
    return parent[curr]

def union(a, b):
    a = find(a)
    b = find(b)
    parent[b] = a

arr = [int(input()) for _ in range(P)]

ans = 0
for g in arr:
    p = find(g) // 내가 지금 도킹하려는 게이트
    if p == 0:
        break
    ans += 1
    union(p-1, p) // 이전 게이트랑 union

print(ans)

---

실수

원리를 다 이해하고서도 계속 틀렸었는데, 그 이유는 진짜 어이없게도 입력으로 들어온 게이트 넘버와 도킹할 수 있는 게이트 넘버를 구분하지 않고

for g in arr:
    # ...
    union(g-1, g)
    # ...

이렇게 해버려서 모든 경우마다 도킹이 가능하다고 떴다 ^^.. 바보 어쩜 이렇게 매일같이 실수할 수 있는지 경이로울 따름이다.