단계별로 풀어보기 문제를 보다가 내가 예전에 틀린 문제가 있어서 가져와보았다! 유니온 파인드 개념을 쓰는 문제였는데, 유니온 파인드 개념을 전혀 기억을 못해서 유니온 파인드 개념부터 공부해서 풀었다. 차근차근 한문제씩 풀어 나가는 게 나의 목표이다.
문제 설명
링크 공항에 비행기 p대가 있고, 게이트가 g개 있다. 문제만 읽으면 잘 이해가 가지 않는데, i번째 비행기를 1-g_i번째 게이트에는 무조건 도킹할 수 있어야 하고 도킹할 수 없으면 공항이 폐쇄된다고 한다. (g_i가 input으로 주어지게 된다) 이 말은 즉 i번째 비행기에 대해 input g_i가 들어오고, 이 i번째 비행기는 1-g_i번째 게이트에 세울 수 있다. 최대 몇 대의 비행기를 세울 수 있는지를(세울 수 없어서 공항 폐쇄 직전까지) 답으로 내면 된다.
문제 풀이
유니온 파인드 개념을 알았더라도 풀기 어려웠던 문제 같다.
먼저 유니온 파인드 개념이 무엇이냐면, 그래프 알고리즘에서 등장한다.
- array[i] : i번째 노드의 부모 노드(루트 노드)
라고 했을 때, union이 두개의 disjoint set(루트 노드가 다른 두 그래프)를 합치는 것이고, find가 해당 그래프의 루트 노드를 return 하는 함수이다. 결국 부모 노드를 잘 다룰 수 있으면 된다. 따라서 union(x, y)는 x와 y의 루트 노드들을 각각 찾고(px, py라고 하겠다) px의 부모 노드를 py로 설정해주면 된다(array[px]=py). find함수는 array[i]=i인 경우 자신의 루트노드이므로 탐색을 멈추고 자신을 return하면 되고, 자신의 루트노드가 아닌 경우는 i의 부모 노드(array[i])에 대해 find함수를 재귀로 한번 더 돌려주면 된다. 여기서 중요한 점은 시간초과를 해결하는 것인데, 메모이제이션을 이용해 return 직전에 i의 부모 노드를 find(i)로 설정해 주면 된다. 즉 부모 노드가 현재 i의 부모 노드의 부모 노드일 수 있기 때문에, 계속 갱신해주면 된다.
아래 문제는 유니온 파인드 개념을 사용하면 풀 수 있는데, 나는 바로 떠올리지는 못했다. i번째 비행기는 1-g_i게이트들에 위치할 수 있는데, 이미 누군가 g_i게이트에 비행기를 세워 놓았으면 g_i-1에 비행기를 세워야 한다. 따라서 각 비행기를 세울 때마다 몇 번째 게이트에 세울 지 또 탐섹해야하기 때문에 O(p*g) 시간이 걸리게 된다. 따라서 각각의 비행기에 대해 몇 번째 게이트에 세우면 되는지 바로 알 수 있어야 한다. 이것은 어떻게 할 수 있냐면, 해당 비행기가 특정 게이트 x에 세워 졌다면, 그 다음 비행기는 무조건 x-1에 세워야 하므로 특정 게이트 x와 x전에 세워진 게이트들과, x-1번째 게이트를 union시켜주면 된다. 즉 내가 세운 게이트의 부모 노드를 내가 세운 게이트 바로 전 노드로 설정해주면 된다. 이렇게 하면 이후에 내가 x번째 게이트에 다시 세우려고 시도할 때, x-1번째 게이트의 부모부터 고려할 수 있게 된다.
코드는 아래와 같다.
1 | |
