[실전 알고리즘] 부록 D - Union-Find

 

 

 

네 반갑습니다. 이번 부록 D에서는 Union-Find 자료구조를 익혀보겠습니다. 지금까지 부록 A, B, C는 크게 까다로운 것 없이 되게 무난했는데 이번 부록 내용은 원래 강의 단원에 넣기에는 좀 난이도가 있어서 뺐던 내용이라 아마 좀 어려울 수도 있습니다. 물론 그렇다고 해서 진짜 뭐 말도 안되게 어렵다거나, 한번 봐서는 이해가 힘들거다 이정도 수준은 아니기 때문에 너무 걱정은 하지 마시고 천천히 같이 익혀보겠습니다.

 

 

먼저 Union-Find 자료구조가 무엇이고 어떤 연산을 지원하는지를 살펴보고 다음으로 각 연산이 어떻게 구현되는지를 볼 예정입니다. 사실 Union-Find에서 가장 중요한건 최적화를 통해서 시간복잡도를 떨구는 것이기 때문에 해당 부분도 보고 연습문제를 풀어보면 강의가 끝납니다. 그래서 사실상 부록이라기 보다는 자료구조를 익히는 정규 단원 한 단원을 더 배운다라고 생각하면 됩니다.

 

 

Union-Find, 혹은 Disjoint-set 이라고 부르는 이 자료구조가 무엇인지를 알아보기 전에 이 강의에서 Union-Find가 처음 등장했던 순간을 잠깐 회상해보겠습니다. 강의에서 Union-Find가 처음 나온건 0x1B강 최소 신장 트리 단원이었는데, 당시에 크루스칼 알고리즘을 익히면서 효율적인 구현을 하기 위해서는 Union-Find 자료구조가 필요하다고 언급했습니다.

 

 

크루스칼 알고리즘은 가장 비용이 낮은 간선부터 시작해 간선을 크기 순으로 살펴보며 서로 떨어져있던 정점들을 합쳐나가서 최소 신장 트리를 만들어내는 알고리즘입니다. 정점의 색깔이 그룹을 나타낸다고 했을 때, 1과 4를 연결하는 간선을 살펴본 후 두 정점의 색을 같게 만든 것이 정점을 합친 것을 나타냅니다.

크루스칼 알고리즘 과정에서 우리가 계속 해야하는 연산은 두 정점이 같은 그룹인지 아닌지 확인하고, 다른 그룹이라면 둘을 합치는 연산입니다. 이걸 Flood Fill로 구현을 하면 O(V+E)의 시간이 필요하지만 Union-Find를 이용하면 두 연산 모두를 사실상 상수 시간에 가까운 속도로 처리할 수 있습니다.

 

 

정리를 해보면 Union-Find에서 지원하는 연산은 말 그대로 Union 연산과 Find 연산 이 2개입니다. Union 연산은 두 그룹을 합치는 연산이고 Find 연산은 특정 원소가 속해 있는 그룹을 알아내는 연산을 말합니다. 크루스칼 알고리즘에서는 두 정점이 같은 그룹인지를 확인하는게 필요하다고 했는데, 두 정점 각각에 대해 Find 연산을 수행하고 나면 자연스럽게 두 정점이 같은 그룹인지를 알 수 있습니다.

 

 

이걸 직관적으로 구현을 한다고 하면, 배열에 각 원소의 그룹 번호를 써둔 다음에 Union이나 Find 연산이 주어질 때 마다 이 값을 가지고 처리를 하는 방식을 먼저 생각을 할 수 있습니다. 일단 처음에는 각 원소의 그룹 번호가 다 다르다고 쳐서 이렇게 세팅을 해둘 수 있습니다. Find 연산의 경우에는 그냥 연산이 들어올 때 마다 배열에 적힌 값을 반환해주면 되니 따로 언급할 것이 없고, Union 연산이 중요한데 여기서 1과 5를 Union하면

 

 

이렇게 5번 원소의 그룹을 1로 바꿔주면 됩니다. 편의상 이번 예시에서는 Union을 할 때 뒷쪽 원소의 그룹을 앞쪽 원소의 그룹으로 합친다고 생각을 하겠습니다. 다음으로 Union 2, 3을 하면

 

 

3번 원소의 그룹을 2로 바꾸면 됩니다. 그러면 여기서 질문으로 Union 연산의 시간복잡도는 얼마일까요? 지금까지 살펴본 내용만 보면 O(1)이 아닌가 하는 생각을 할 수도 있지만 여기서 Union 1, 3을 수행하려고 한다면 이전과 다른 상황이 발생한다는걸 확인할 수 있습니다.

 

 

Union 1, 3을 수행할 때 3번 원소의 그룹만을 1번으로 바꾸면 뭔가 좀 이상합니다. 아까 Union 2, 3으로 인해 2번과 3번 원소가 한 그룹이 되었기 때문에 이번에 Union 1, 3를 하고 나면 2번 원소의 그룹도 같이 바꿔줘야 합니다. 정리를 해보면 Union u, v 명령이 들어오면 u의 그룹을 확인하고, 전체 원소를 살펴보면서 v와 같은 그룹인 모든 원소들의 그룹을 u의 그룹으로 바꿔줘야 합니다. 그렇기 때문에 각 원소의 그룹을 배열로 관리하는 지금의 구현 방식에서 시간복잡도를 살펴보면 Find는 O(1), Union은 O(N)입니다. 반면 실제 Union-Find 자료구조에서는 두 연산 모두가 거의 상수 시간에 해결이 가능합니다. 과연 실제로는 어떤 방식으로 구현이 이루어져 있길래 그게 가능한건지 같이 알아보겠습니다.

 

 

실제 구현에서는 각 원소를 정점으로 생각하고 그룹은 트리로 표현한 다음 Union 연산이 발생할 때 마다 한 트리의 루트가 다른 트리의 자식으로 들어가서 두 개의 트리가 합쳐집니다. Union 연산을 하는걸 한 번 보면 쉽게 무슨 뜻인지 이해할 수 있습니다. 그리고 이 트리 구조를 실제 코드로 저장할 때에는 각 원소에 대해 부모 정점의 번호를 담을 배열을 만들고 값을 적절하게 쓰면 됩니다. 일단 처음에는 모든 원소에 대해 부모 정점이 없다는 뜻으로 -1을 채워두고 Union 1, 5를 하면

 

5번 정점을 1번 정점의 자식으로 만듭니다. 다음으로 Union 2, 3을 하면

 

 

자연스럽게 3번 정점을 2번 정점의 자식으로 만들면 되고, 여기서 Union 1, 3를 하면

 

 

그 전과는 다르게 3번 정점을 1번 정점의 자식으로 만들면 안됩니다. 그렇게 되면 2번 정점이 낙동강 오리알 신세가 되어버리기 때문에 3번 정점이 속한 그룹 전체가 1번 정점이 속한 그룹과 합쳐질 수 있도록 하려면 3번 정점이 속한 그룹의 루트인 2번 정점을 1번 정점의 자식으로 만들어야 합니다. 이렇게 2번 정점을 1번 정점의 자식으로 만들고 나면 1, 2, 3, 5가 같은 트리에 속하기 때문에 같은 그룹인게 눈에 바로 보입니다. 마지막으로 Union 2, 6을 해보겠습니다.

 

 

Union 2, 6을 할 때에는 6번 정점이 속한 그룹의 루트를 2번 정점이 속한 그룹의 자식으로 만들면 됩니다. 사실 6번 정점을 루트인 1번 정점 대신 그냥 2번 정점의 자식으로 둔다고 해도 문제가 있는건 아니지만 Union u, v를 할 때 u와 v 모두에 대해 루트를 확인하면 혹시 u와 v가 같은 그룹인지를 판단할 수 있습니다. 그렇기 때문에 v의 루트를 u의 자식으로 만드는게 아닌, v의 루트를 u의 루트의 자식으로 만든다고 생각하겠습니다.

 

이렇게 Union을 살펴보았고 어떻게 동작하는지는 충분히 이해가 됐을거라고 생각하는데, 실제 구현 방식이랑 시간복잡도는 Find 연산까지 보고난 후에 같이 얘기를 나눠보겠습니다.

 

 

Find 연산에서는 내가 속한 그룹의 번호를 알아내야 하는데, 다른 말로 표현하면 내가 속한 트리의 루트를 구하면 됩니다. 지금 상황에서 1, 2, 3, 5, 6번 원소의 그룹의 번호는 1이고, 4, 7, 8, 9, 10번 원소의 그룹의 번호는 자기 자신입니다. 그리고 이걸 구현할 때에는 루트에 도달할 때 까지 계속 부모 정점을 타고 올라가면 되는데, 3번 원소의 그룹을 찾는걸 한 번 보면 금방 이해가 될 수 있습니다. Find 3을 같이 해보겠습니다.

 

 

Find 3을 하기 위해서 일단 3번 정점의 부모 정점을 확인합니다. 부모 정점이 2번이기 때문에 먼저 2번으로 올라가면 됩니다.

 

 

2번 정점에 도착한 다음에는 마찬가지로 2번 정점의 부모 정점을 확인합니다. 부모 정점이 1번이기 때문에 1번으로 올라가면 됩니다.

 

 

1번 정점에 도착한 다음에는 다시 1번 정점의 부모 정점을 확인하면 되는데, 1번 정점의 부모 정점은 -1로 기록이 되어있고 이 말은 곧 1번 정점이 루트임을 나타내기 때문에 여기서 올라가는걸 중단하고 3번 정점의 그룹 번호가 현재 정점의 번호인 1임을 알 수 있습니다.

 

 

부모 정점이 저장된 배열을 p라고 할 때, 우선 find 연산부터 구현을 해보겠습니다. 다음 슬라이드에 코드가 바로 나오고 또 코드가 비교적 단순하긴 해서 굳이 직접 타이핑까지는 안해보셔도 되지만 한번 나라면 어떤식으로 구현을 할까 형태를 한 번 고민해보시는걸 추천드립니다.

 

 

이렇게 코드는 그냥저냥 단순합니다. 반복문으로 작성해도 되지만 그냥 재귀로 짰는데, 지금 이 강의를 보고 계실 정도면 재귀가 그렇게 막 부담스럽지는 않겠죠? p[x]가 음수이면 x가 루트라는 의미이니 x를 반환하고, 그렇지 않으면 find(p[x])를 반환하면 자연스럽게 부모로 한 단계씩 올라가면서 루트를 찾게 됩니다.

 

 

다음으로는 Union을 구현해볼건데, 앞에서 Union u, v를 하던 과정을 다시 떠올려보면 u가 속한 트리의 루트를 찾고 v가 속한 트리의 루트를 찾은 후 v가 속한 트리의 루트를 u가 속한 트리의 루트의 자식으로 만들었습니다. 이걸 코드로 옮기면 되는데, Find와 마찬가지로 한 번 머릿속으로 고민해보고 나서 다음 슬라이드를 확인해봅시다. 그리고 함수 이름이 uni인 이유는 아쉽게도 union이 공용체를 의미하는 예약어여서 함수 이름으로 쓸 수 없어서 그런거고, 또 자료형이 bool인 이유는 만약 u와 v가 이미 같은 그룹이어서 Union을 할 필요가 없으면 false를, 다른 그룹이어서 Union이 정상적으로 이루어졌으면 true를 반환하고자 하는 목적입니다.

 

 

여기 코드를 같이 확인해보면, 일단 u와 v 모두 find를 해서 루트의 번호를 u와 v에 대입시킵니다. 만약 두 개가 같다면 둘이 같은 그룹이라는 의미이기 때문에 false를 반환하면 되고, 그렇지 않다면 v의 부모를 u로 바꾼 후 true를 반환하면 됩니다. 크게 어려운건 없습니다.

 

 

이제 시간복잡도를 같이 생각해볼건데, Union의 경우에는 u, v 각각에 대해 find를 수행한 뒤에 12-15번째 줄에서 처리하는 일은 그냥 O(1)입니다. 그렇기 때문에 Find 함수의 실행 시간이 전체 시간복잡도를 따질 때 중요하게 작용합니다. 그리고 Find 함수는 부모를 타고 한 단계씩 올라가는 방식으로 구현이 되어 있기 때문에 각 정점에 대해 Find 함수를 적용할 경우 해당 정점의 깊이만큼의 시간이 필요합니다.

 

 

문제는 최악의 경우 정점의 깊이가 최대 N이 될 수 있다는 점입니다. 예를 들어 Union 2, 1 / Union 3, 2 / Union 4, 3 / Union 5, 4 / Union 6, 5 이런식으로 Union을 적용한다면 이렇게 일자인 트리를 별로 어렵지 않게 만들 수 있고 이 상황에서 Find 1은 O(N)에 동작합니다. 이러면 처음의 직관적인 구현이 시간복잡도가 안 좋아서 트리를 이용해 Union-Find 자료구조를 만든게 아무 의미가 없게습니다.

 

사실 정식 Union-Find는 여기에다가 뒷 챕터에서 소개할 최적화를 추가로 적용해야 우리가 원하는 효율적인 자료구조로 쓸 수 있습니다. 만약 최적화를 적용하지 않게 되면 지금 본 것과 같이 Union과 Find 모두 최악의 경우 O(N)에 동작하는 비효율적인 구조가 된다는 점을 꼭 기억합시다.

 

Union-Find 자료구조에 적용할 수 있는 최적화는 2가지가 있는데, 첫 번째로 Union by rank를 알아보겠습니다. 만약 지금 슬라이드처럼 트리를 만들어 놓은 상태에서 Union 7, 2를 하고자 한다면 앞의 코드에서 p[v] = u로 작성한 것 처럼 7번 원소가 속해있는 트리의 루트는 1번, 2번 원소가 속해있는 트리의 루트는 2번이니 자연스럽게 1번 정점을 7번 정점의 자식으로 두게 됩니다.

 

 

그런데 트리의 높이를 최대한 낮추는게 실행 시간 면에서 유리한데, 1번을 7번의 자식으로 두는 대신 7번을 1번의 자식으로 두면 전체적으로 트리의 높이를 더 낮게 유지할 수 있습니다. 즉 Union을 할 때 그냥 무조건 p[v] = u를 하는게 아니라, u가 속해있는 트리의 높이와 v가 속해있는 트리의 높이를 비교한 다음 더 낮은 트리를 높은 트리의 자식으로 붙이는 최적화를 할 수 있습니다. 그리고 이 높이를 랭크라고 부를 예정입니다. 그러면 왜 이 최적화의 이름이 Union by rank인지 이해를 할 수 있을거라고 생각합니다.

 

Union by rank를 위해서는 각 그룹이 속해있는 트리의 랭크를 관리하고 있어야 하는데, rnk와 같은 별도의 배열을 둘 수도 있겠지만 제가 좋아하는 구현 방식은 부모 정점을 저장하는 p 배열 안에서 랭크도 같이 관리하는 방식입니다. 이전에는 p 배열에서 값이 양수이면 부모의 정점을 의미하고 값이 -1이면 해당 정점이 루트임을 의미했는데, 트리의 높이가 증가함에 따라 -1을 -2, -3, -4 이렇게 만들 예정입니다. 실제 Union을 하는 예시를 보면서 이해해보겠습니다.

 

일단 처음 시작은 별반 다를거 없이 전체를 -1로 초기화해둡니다. -1의 의미는 해당 정점이 루트이고 또 트리의 높이가 1임을 의미합니다.

 

 

여기서 Union 1, 5를 하면 1과 5 둘 다 트리의 높이는 1로 동일하니 1을 5의 자식으로 만들어도, 5를 1의 자식으로 만들어도 상관없습니다. 일단 5를 1의 자식으로 만들었다고 생각하겠습니다. 그렇게 되면 p[5]를 1로 변경하고, 그와 함께 p[1] 또한 -2로 변경합니다. p[1] = -2라는 것은 1이 루트인 트리의 높이가 2임을 나타냅니다.

 

 

다음으로 Union 2, 3을 비슷하게 p[3] = 2로 바꾸고, p[2]도 높이가 2가 되었다는 의미로 p[2] = -2로 변경합니다.

 

 

다음으로 Union 4, 3을 하려고 합니다. 그러면 먼저 Find 4를 해서 4가 속한 그룹의 루트가 4인걸 알아내고, 또 Find 3을 해서 3이 속한 그룹의 루트가 2인걸 알아냅니다. 그리고 2의 랭크와 4의 랭크를 비교하면 4의 랭크가 더 낮기 때문에 4를 2의 자식으로 만들어서 p[4] = 2로 바꾸면 됩니다. 또 랭크가 동일한 두 그룹을 합치면 높이가 1 늘어나니 랭크 또한 1 늘어나겠지만 지금처럼 랭크가 낮은 그룹을 높은 그룹에 합칠 때에는 트리의 높이가 그대로이기 때문에 랭크가 바뀌지 않습니다. 그래서 p[2]는 -2로 그대로 두면 됩니다.

 

 

마지막으로 Union 1, 4를 하면 각각이 속한 그룹의 루트인 1, 2를 찾고 랭크를 비교하는데 랭크가 동일하니 둘 중 아무거나 선택해서 다른 하나의 자식으로 두면 됩니다. 2를 1의 자식으로 둔다고 하면 p[2] = 1로 바꾸고, 1의 랭크 또한 1 증가시켜서 p[1] = -3으로 바꾸면 됩니다. 이렇게 Union을 할 때 트리의 높이를 고려해서 합치는 최적화를 Union by rank라고 합니다.

 

 

이걸 코드로 옮겨보면 먼저 루트를 찾은 후 랭크에 따라 적절하게 처리를 하면 됩니다. p[u], p[v]에 랭크는 음수로 저장되어 있는걸 꼭 인지한 상태로 코드를 확인해봅시다. 예를 들어 p[v] < p[u]는 v의 랭크가 u보다 클 때 true이고, 또 u의 랭크를 1 증가시키는게 p[u]-- 입니다.

 

 

두 번째 최적화 방법은 바로 경로압축으로, Find를 할 때 말 그대로 경로를 압축해 효율적으로 동작하게 만드는 방법입니다. Union-Find 자료구조에서 이런식으로 구조가 생겨있다고 해보겠습니다. 여기서 Find 3을 한다면 기존 Find에서는 3번 정점에서 출발해 부모를 따라 올라가며 루트인 6번 정점에 도달해서 그룹이 6번임을 확인한 후 끝내게 됩니다. 그런데 경로 압축에서는 6번 정점에 도달한 후 처리를 하나 더 하는데, 지나가는 길에 있던 모든 정점들을 전부 6번 정점의 자식으로 만듭니다.

 

 

즉, 지금 슬라이드처럼 Find 3을 하고 나면 3, 4번 정점이 6번 정점의 자식으로 옮겨갑니다. 이렇게 해도 여전히 3, 4번 정점은 6번 정점이 루트인 트리에 속해있으니 구조에 문제가 없고, 트리의 높이는 줄일 수 있습니다. 경로 압축은 간단한 아이디어이면서도 효과적입니다.

 

 

이 최적화를 find 함수에 적용하려면 06번째 줄 처럼 기존에는 그냥 find(p[x])를 반환하던걸, p[x]에 대입까지 할 수 있게 p[x] = find(p[x])로 바꿔주면 끝입니다. 이렇게 하면 자연스럽게 루트까지 가는 경로 상으로 거치게 되는 각 x에 대해 부모, 즉 p[x]가 루트로 바뀌게 됩니다. 이렇게 최적화를 적용하고 나면 Union-Find 자료구조가 원하던대로 효율적으로 동작합니다. (코드)

 

 

그래서 구체적인 시간복잡도가 얼마냐고 하면, 원소의 수가 N개라고 할 때 최적화 1만 적용을 한다면 트리의 높이가 최대 log N으로 제한되어서 각 연산의 시간복잡도가 O(log N)입니다. 그리고 최적화 2만 적용을 한다면 이 경우에는 Amortized O(log N)이 되는데, Amortized는 동적 배열 단원에서 처음 언급드렸지만 연산을 한 번 할 때에는 운이 나쁘면 O(N)이 걸릴 수도 있습니다. 예를 들어 트리가 일자로 생겨있는 상황에서 리프 원소를 잡고 Find를 한다면 O(N)이 걸립니다. 하지만 Find를 하고 나면 트리의 높이가 2로 낮아지기 때문에 또다시 Find를 한다면 그 때에는 O(1)입니다. 이런식으로 M번의 연산을 할 때 매번 연산의 시간복잡도는 O(N), O(1), 이렇게 다양할 수 있지만 전체 시간을 합쳐보면 O(MlogN)이 된다는 의미입니다.

 

흥미로운건 최적화 1과 최적화 2를 같이 적용했을 때인데, 둘을 같이 적용하면 지금까지 한 번도 등장한 적 없는 Amortized O(α(N))이라는 시간복잡도가 나옵니다. 이 α(N)은 정확히는 애커만 역함수라고 이름 붙은 함수인데, 저 함수가 무엇이고 왜 저런 시간복잡도를 가지는지는 너무 나간 얘기라 생략하겠습니다. 하나 알고가면 되는건, 저기 적어놓은 것 처럼 N이 무려 2^2^2^65536-3이하일 때 α(N)이 4 이하이기 때문에 우리가 현실적으로 사용할 N의 범위에서는 사실상 상수 취급을 하면 된다는 점입니다. 그래서 Union-Find 자료구조에서 연산의 시간복잡도가 "사실상" 상수 시간이라고 강조를 했던 것입니다. 그리고 실제로 문제를 풀 때 코드를 짠다면, 최적화 2개를 다 적용하면 물론 가장 성능이 좋겠지만 Amortized O(log N)도 충분히 빠릅니다. 그렇기 때문에 최적화를 아예 적용하지 않으면 문제가 되겠지만, 둘 중에서 하나만 적용을 한다고 하면 그걸로 인해서 시간초과가 발생할 가능성은 거의 없다고 보시면 됩니다. 어쨌거나 강의에서 2가지 최적화를 모두 소개해드렸으니 뒤의 연습문제에서는 2가지 최적화를 모두 적용해서 예시 코드를 작성하겠지만 여러분들의 경우에는 굳이 그렇게 할 필요는 없습니다. 둘 중 하나만 적용해도 전혀 문제 없고, 또 아무래도 Union by rank보다는 경로 압축이 코드가 훨씬 더 간단하니 그냥 경로 압축만 적용을 하셔도 아무 상관 없습니다.

 

 

이제 즐거운 연습 문제 풀이 시간입니다. 첫 번째 문제는 BOJ 1717번: 집합의 표현인데 문제를 보면 그냥 대놓고 Union-Find를 써서 풀면 되는 문제이구나 하는게 감이 옵니다. 집합을 합친다는건 Union에 대응되고 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산은 Find에 대응됩니다. 제가 앞에서 작성한 Union-Find 코드를 바탕으로 이 문제의 코드를 작성해봅시다.

 

 

코드에서 특별히 꼭 강조를 해야하는 부분은 따로 없어 보입니다. q = 0일 땐 union을 하고, q = 1일 땐 find(a)와 find(b)를 해서 각각의 루트를 찾고 일치하는지 확인하면 끝입니다. 지금의 코드는 최적화 1과 2를 모두 적용한 코드인데, 그냥 개인적으로 궁금해서 최적화 1만 적용해서 내보고, 다음으로 최적화 2만 적용해서 제출해봤습니다. 그런데 세 경우 모두 32ms로 실행 시간이 동일했습니다. 물론 이론적으로는 최적화 1과 2를 적용한게 제일 좋고, 또 실행 시간은 테스트케이스에 따라 차이가 있을 수 있지만, 아무튼 최적화를 1개만 적용한다고 해서 큰 문제가 안된다는걸 확인할 수 있습니다. 

 

 

다음 문제는 BOJ 7511번: 소셜 네트워킹 어플리케이션입니다. 지금 다루는게 Union-Find니까 당연히 Union-Find로 풀리겠지만, Union-Find 말고도 그 전에 배운 알고리즘으로도 풀리겠네 하는 생각을 하실 수 있다면 참 좋을텐데 혹시 감이 오실까요?

 

이 문제는 BFS로도 해결이 가능합니다. 미리 친구 관계가 주어진걸로 그래프를 다 만들어놓고 BFS를 한 번 돌리고 나면 그 뒤로 두 사람이 주어질 때 마다 서로 방문이 가능한지, 문제의 표현대로면 경로가 존재하는지를 판단할 수 있습니다. 어떻게 보면 BOJ 1717번: 집합의 표현 문제에서 q = 0인 쿼리를 먼저 앞에 모아서 보내고 다음으로 q = 1인 쿼리를 하나씩 처리하는, 이전 문제의 쉬운 버전이 지금 이 7511번 문제라고 생각할 수 있습니다. 다른 말로 표현하면 지금 7511번 문제는 Union-Find와 BFS 모두로 풀리는데, 만약 문제를 살짝 바꿔서 친구 관계가 주어지는거랑 경로가 존재하는지를 판단하는거랑 순서가 섞여서 주어진다면 BFS로는 해결이 안됩니다. 그래서 약간의 팁을 드리자면, 아무래도 여러분은 지금 막 배운 Union-Find 보다는 수도 없이 문제를 많이 풀어봤을 BFS가 더 친숙할 것입니다. 그래서 뭔가 문제를 접했을 때 혹시 BFS가 되나 하고 고민을 해보는 경우가 많을텐데, BFS로 풀릴듯 말듯한데 약간 미묘하게 해결이 안되는 지점이 있는 경우라면 그 문제를 사실은 Union-Find로 풀어야 하는 것일수도 있습니다.

 

설명이 길어졌는데, 다시 문제로 돌아오면 이 문제를 Union-Find로 어떻게 풀면 될지는 금방 감이 올 것입니다. 심지어 이전 문제의 하위호환이니까요. 직접 한 번 짜보시고 다음 슬라이드에서 코드를 확인해봅시다.

 

 

코드를 보면 find, uni는 똑같으니 생략하고, 문제 한글 설명 기준으로 처음에 테스트케이스의 수가 주어진다는 얘기가 빠져있긴 한데 이정도는 그 동안 문제를 풀어온 짬바로 적당히 넘어가고, 새로운 테스트 케이스가 시작할 때 마다 24번째 줄처럼 p를 초기화하는걸 꼭 신경써야 합니다. 그 뒤는 그냥 자연스러운 흐름이어서 설명은 생략하겠습니다.

 

 

이번 강의에서는 Union-Find 자료구조를 배우고 관련 문제를 풀어봤습니다. 사실 코딩테스트 기준으로는 Union-Find가 꽤 어려운 편에 속하는 자료구조이지만 지금 이렇게 부록 D까지 보실 정도면 앞 부분의 내용들은 꽤 숙지가 된 상태이실테니 화룡점정을 이룬다는 느낌으로 제공해드릴 문제를 풀어보면서 Union-Find를 응용하면 어떤 문제들이 나올 수 있는지를 익혀보시는걸 추천드립니다. 그럼 고생하셨습니다.