호프크로프트-카프 알고리즘
어떻게 인연이…
이번에 정리할 알고리즘은 호프크로프트-카프(Hopcroft-Karp Algorithm)입니다.
이 알고리즘의 존재에 대해 알게 된 계기가 System Engineer 문제입니다. 대략 일 년 전쯤에 이분 매칭 문제들을 처음 접하고 몇 문제 풀다가 그만 둔 후, 얼마 전부터 다시 풀기 시작했습니다. 그동안 제가 맞닥뜨린 이분 매칭 문제들은 이분 그래프를 만들고 어떤 조건으로 매칭시킬지만 고민했던, DFS 방식만으로도 풀리는 문제였습니다. 그런데 System Engineer 문제는 기존 방법으로 코드를 작성해서 제출하니 시간초과 판정을 받았습니다. 여러 번의 실패 끝에 뒤늦게 무언가 이상하다고 느꼈습니다. 알고보니 영어로 작성된 문제라 유심히 보지 않았었는데, 이 문제는 n 크기가 10,000입니다. 그리고 다른 사람의 코드 길이와 시간복잡도를 보고 저랑 다르다는 걸 깨달았습니다. 즉, 제가 써왔던 기존 방법으로는 풀 수 없는 문제입니다. C++이면 몰라도 파이썬으로는 안 풀립니다.
사실 1만인 걸 알고도 혹시나 싶어서 제출을 했어요… 태양이 뜨거운지 꼭 만져봐야 아는 사람
제출 기록에서 보이는 것처럼 수많은 실패를 하고서야 이상하다는 걸 깨달았습니다. Attribute error는 부끄럽네요
이래서 문제를 꼼꼼히 읽고 조건을 파악해야 합니다. 매번 실수하는 거 보면 백종원도 솔루션 포기할 듯
마침 이분 매칭에 흥미를 느껴 관련 문제들을 풀던 시기라 저는 이번 기회에 새로운 알고리즘을 공부하려고 마음 먹었습니다. 그리고 이 문제를 호프크로프트-카프 알고리즘으로 풀 수 있다는 사실을 알아냈습니다. 디닉 알고리즘은 들어봤어도 이거는 듣도 보도 못했던 알고리즘이었는데, 보자마자 쉽진 않겠다는 생각이 들었습니다. 평소에 플로우 공부를 안 했으니까 모르지
호-카 알고리즘이란
서론이 길었습니다만 본론도 깁니다. 지금부터 호프크로프트-카프 알고리즘입니다.
정점의 개수와 간선의 개수가 각각 N과 M일 때, 이 알고리즘은 시간복잡도가 O(M√N)이라는 점에서 특이합니다. 완전 이분 그래프를 가정한다면 시간복잡도가 O(N^2.5)이 되겠네요. 루트가 있다는 점에서 흥미롭습니다!
기본적인 개념을 다시 짚어보죠. 그래프 G = (V, E)이고 M ⊆ E 라고 다시 정의하겠습니다. 그러니까 간선 집합을 E라고 할 때, 매칭(Matching) M은 정점을 서로 공유하지 않는 간선의 부분집합입니다. 이때 매칭된 간선의 정점(끝점)은 matched 상태이며, 그렇지 않은 정점을 exposed 상태라고 우리는 알고 있습니다.
그리고 새로운 개념으로 두 가지 경로에 대해 알아봅시다.
- Alternating Path : 매칭 M에 속하는 간선과 속하지 않는 간선을 번갈아가며 이은 경로를 말합니다. 모든 매칭을 포함하지 않아도 됩니다.
- Augmenting Path : 어떤 Alternating Path의 양 끝에 있는 점이 모두 exposed 상태인 것을 말합니다.
따라서 Augmenting Path라면 경로에 속하는 간선이 매칭에 속하는지 여부를 따졌을 때, False - True - False - True - False 이런 식으로 나타납니다. 당연히 길이(간선 개수)는 홀수예요.
이제 정점 그룹 A와 B로 만든 아래의 이분 그래프를 예를 들어보겠습니다. 붉은 간선이 매칭입니다.
그리고 아래에서 주황색 형광색으로 이어진 간선 경로는 해당 그래프에서 찾을 수 있는 Augmenting Path 중 하나입니다.
그런데 만약에 매칭에 속하는 간선과 매칭에 속하지 않는 간선의 상태를 바꿔주면 어떻게 될까요? 기존에 매칭된 간선은 매칭되지 않은 것으로 바꾸고, 반대로 매칭되지 않았던 간선을 매칭된 상태로 설정하는 거예요. 다음 그림은 해당 경로에 속한 간선의 상태를 바꿔준 모습입니다. 파란 간선이 새로 생긴 매칭입니다.
눈치채셨나요? (≧∀≦) 이제 Augmenting Path의 이름이 가진 의미를 알 수 있습니다. 방금처럼 경로의 간선 상태를 반전시키면 새로운 매칭을 얻을 수 있는데, 이 새로운 매칭은 기존의 매칭보다 간선이 하나 더 많습니다. 따라서 만약 Augmenting Path가 존재한다면 매칭 M의 크기가 더 커질 수 있다는 점을 알 수 있습니다. 또한, 결론적으로 현재 매칭 상태에서 새로운 Augmenting Path를 찾을 수 없다면, 최대 매칭 상태임을 알 수 있습니다. 사실 마지막 그림은 최대 매칭 상태입니다. 그림에서 exposed 상태인 정점 두 개를 끝점으로 하는 Augmenting Path를 만들 수 없기 때문이에요.
호프크로프트-카프 알고리즘은 앞서 설명한 Augmenting Path의 성질을 이용합니다. Augmenting Path를 P, 앞서 설명한 것처럼 경로 간선 상태 반전 작업을 M ⊕ P라고 한다면 그래프 G = (V, E)가 있을 때, 다음과 같은 과정으로 최대 매칭을 찾습니다.
- M이 공집합인 상태에서 시작한다.
- L = 현재 M에서 찾을 수 있는 가장 짧은 P의 길이.
- 길이가 L이고 서로 정점을 공유하지 않는 P 집합을 최대로 찾는다.
- M = M ⊕ P1 ⊕ P2 ⊕ P3 ….
- 현재 M에 P가 없다면 멈추고, 그렇지 않다면 2번 과정부터 반복한다.
또한 위 과정을 구현한 코드 내용은 아래와 같이 요약할 수 있습니다.
- 이분 그래프에서 기준 그룹을 정한다. 예시로 기준 그룹을 A, 상대 그룹을 B라고 하겠습니다.
- A 그룹에서 exposed 상태의 정점 레벨을 0으로 설정한다.
- Alternating Path를 따라 정점마다 레벨을 부여한다(BFS 과정).
- B 그룹의 정점이 이미 matched 상태이며, 서로 매칭된 A 그룹의 정점의 레벨이 정해지지 않은 상태라면 레벨을 새로 부여한다.
- 0 레벨 정점부터 Augmenting Path를 찾는다.
- B 그룹의 정점이 exposed 상태이거나 서로 매칭된 A 그룹 정점의 레벨이 현재 정점 레벨에서 1 더한 값이라면 새로운 Augmenting Path를 찾는다.
- Augmenting Path를 찾을 수 없을 때까지 2번 과정부터 반복한다.
이 글은 해당 알고리즘에 대해 개인적으로 기록해서 공부하기 위해 썼으며, 추후에 내용이 추가될 수 있습니다.