아마 플로우 관련 게시글 중엔 드디어 마지막이 될 겁니다. 아마. 더 아는 게 없습니다 제가...
이번 글에서 다룰 내용은 역시 국내 자료가 하나도 없는 호프크로프트 카프 알고리즘(Hopcroft-Karp algorithm). 아니 구글에 쳐도 무슨 이상한 광고만 나오고;
이거봐요... 진짜 뭐 관련있는 것도 없습니다.
알고리즘이란 키워드를 덧붙여 봐도, 과정을 설명한 글은 찾을 수 없었습니다. 같이 나오는 라빈 카프 알고리즘은 덤입니다... 쥬륵 ㅠㅠ
물론, 영미권에서 검색하면 자료가 쏟아져 나오겠지요. 저도 영어자료로 공부했고...
이것도 더 빠른 최대 유량 알고리즘인데, 이분 그래프라는 특수한 상황에서만 동작합니다.
이분 매칭을 더 빨리 하는 것인데, 시간복잡도는 괴상하게도 O(E√V)입니다. 루트 V.
완전 이분 그래프에서 E = O(V^2)니까 최악이 O(V^2.5)인 거죠.
사실 이 알고리즘은 원래의 이분 매칭과 비슷하게, 디닉 알고리즘을 모든 간선이 용량 1인 이분 그래프 환경으로 국한되게 만든 결과물입니다. 또는 디닉 알고리즘의 특수한 경우가 이것이고, 이것의 확장판이 디닉 알고리즘과도 같은 것이죠.
그래서 디닉 알고리즘과 코드가 굉장히 닮아 있습니다. 디닉과 기존의 이분 매칭 코드를 반반씩 섞어 놓은 느낌입니다.
이 알고리즘은 말했듯이 간선 용량이 모두 1인 이분 그래프에서만 작동하고, 최대 매칭을 찾는 빠른 알고리즘입니다.
이때 매칭(matching)은 여태까지 그래왔듯이 간선 집합 E의 부분집합인데, 끝점이 하나도 겹치면 안 되죠. 매칭의 크기는 매칭의 개수이고요.
이때 현 상태에서 추가할 수 있는 간선이 하나도 없을 경우, 다시말해 매칭의 크기를 늘릴 방법이 하나도 없다면 maximal matching이며,
크기가 모든 솔루션 중 최대인 매칭이 maximum matching입니다.
이때 말고도 maximal, maximum은 컴퓨터과학계에서 이런 차이로 많이들 쓰입니다.
이 알고리즘에서 추가적으로 정의하는 용어가 2개 있습니다. 두 정점 그룹을 A, B라 합시다.
① 교차 경로(alternating path): 그래프 위의 경로인데, 어떤 매칭 M에 대해 매칭에 속한 간선 - 속하지 않은 간선 - 속한 간선 - 속하지 않은 간선 - ... - 속한 간선 순으로 번갈아가며 속하는 규칙이 반복되는 경로
② 증가 경로(augmenting path): 양 끝점은 매칭에 속하지 않고, 나머지 경로가 교차 경로를 이루는 경로
(한글 용어는 용이한 설명을 위한 의역입니다. 평소엔 그냥 영어 단어를 사용하시는 걸 추천합니다.)
예를 들어, 이런 그래프가 있고 빨간색으로 표현된 간선들이 매칭일 때,
위 그림에서 녹색 경로 [A1, B1, A2, B3]은 일종의 교차 경로입니다.
꼭 매칭에 속한 모든 간선을 포함하지는 않아도 됩니다.
그리고 위 그림에서 녹색 경로 [B2, A1, B1, A2, B3, A4]는 일종의 증가 경로입니다.
왜 용어에 증가 경로라는 이름이 붙었느냐? 유량 그래프에서 새로 유량을 흘릴 수 있는 경로를 증가 경로라고 불러왔는데 말입니다.
왜냐면, 증가 경로가 존재하면 반드시 매칭 크기를 1 늘릴 수 있기 때문입니다.
어떤 증가 경로가 있으면, 간선이 경로순으로 안 속함 - 속함 - 안 속함 - 속함 - ... - 속함 - 안 속함 상태죠?
그런데 이 모든 간선의 속함 여부를 다 뒤집어버리면, 어때요? 원래 매칭에 속해있는 간선 수가 안 속해있는 간선 수보다 항상 1 작았는데, 반대가 되었으니 이제 매칭에 속한 간선 수가 1 증가한 셈이 되죠?
바로 위의 증가 경로를 뒤집어버리면 이렇게 바뀌죠! 매칭이 3에서 4로 증가했습니다.
즉, 호프크로프트 카프 알고리즘의 기본 아이디어는, 이러한 증가 경로가 존재한다면 반드시 매칭 크기는 1 커질 수 있다는 것입니다.
따라서 증가 경로를 가능한 한 계속 찾습니다. 더이상 증가 경로가 없다면 최대 매칭을 찾은 겁니다.
알고리즘의 과정을 말로 설명하자면 이러합니다.
① 매칭 M이 공집합인 상태로 시작한다.
② 서로 정점, 간선이 겹치지 않는 증가 경로의 집합 P를 찾는다.
③ M = M ⊕ P
④ P가 공집합이면 종료하고, 아니면 ②로 돌아가 반복한다.
간단합니다. 그냥 증가 경로 하나가 아니라 집합 P로 바뀐 건데, 그거나 그거나지만 한번에 최대한 많이 찾을 수 있으면 좋겠다는 것이죠.
그리고 ③의 ⊕ 연산자는 XOR 연산입니다. 각 간선이 집합에 속해있으면 true, 아니면 false 값을 가진다고 생각하고 취하면 됩니다.
이걸 이제 또 아트하게 구현하는 점이 문제가 됩니다.
앞서 말씀드렸듯이 디닉 알고리즘과 굉장히 유사하긴 합니다.
먼저 디닉 알고리즘에서 그랬듯이 각 정점에 레벨을 매깁니다. A, B 그룹 상관없이요.
그런데, 이때 레벨 0인 정점들은 먼저 정하고 들어갑니다. A 그룹에 속해 있고(B여도 딱히 상관은 없습니다.) 매칭에 속하지 않은 정점들이 레벨 0입니다.
그 이후는 디닉과 같습니다. BFS를 하여, 다른 정점들의 레벨을 매깁니다. 즉 다른 정점들의 레벨은 모든 레벨 0 정점과의 최단거리 중 최소값이 됩니다.
코드포스 튜토리얼 페이지에서 참고했다는 ppt에 좋은 예제가 있어서 가져왔습니다.
만약 그래프가 이러하고, 현재 매칭이 빨간 선들일 때...
파란 그룹이 A, 빨간 그룹이 B라 하면,
레벨은 이렇게 매겨집니다.
이분 그래프의 특성상, A 그룹엔 짝수 번호만, B 그룹엔 홀수 번호만 존재하죠.
이제 디닉 알고리즘에서처럼, 찾는 증가 경로는 반드시 레벨이 1 증가하는 순으로만 정점들을 거쳐야 합니다. 부가적인 조건은 경로에 든 정점 개수가 짝수 개. 즉, [0, 1, 2, 3], [0, 1] 등의 레벨 순서만 가능합니다.
이 글에서 재정의한 증가 경로의 정의와도 잘 맞아떨어지는 걸 알 수 있죠.
그 다음부터는, 원래 이분 매칭을 하던 것처럼 A그룹의 정점을 슥 훑으면서,
레벨이 0인 정점을 마주치면 그 정점에서 시작하는 증가 경로를 아무거나 하나 찾습니다.
찾을 수도 있고 못 찾을 수도 있습니다. 지금까지 찾은 증가 경로와 안 겹쳐야 하거든요. 정점도, 간선도.
맨 처음엔 이런 증가 경로를 하나 찾았네요. 증가 경로를 하나 찾았다는 말은, 매칭 크기가 1은 늘어날 것이란 의미죠.
그 다음, 이런 증가 경로를 또 찾을 수 있습니다.
마지막으로 이런 증가 경로를 더 찾을 수 있습니다.
이때 원래 이분 매칭에서처럼, 증가 경로끼리 가능하면 경로를 교환하는 경우도 생기게 됩니다.
원래는 간선 [A5, B5]가 이전에 찾은 증가 경로 중에 있었는데, 이걸 [A5, B6]으로 대체하면 이번에 새로 증가 경로 [A6, B4, A3, B5]를 추가할 수 있게 되죠.
결과적으로 증가 경로를 3개 찾았기에, 매칭 크기는 3이 더 늘어날 수 있게 됩니다.
그에 따라 갱신한 매칭은 위와 같습니다. 이게 한 단계를 나타낸 것.
이런 식으로 더 이상 증가 경로를 찾을 수 없을 때까지 이 과정을 반복하면 됩니다.
https://www.acmicpc.net/problem/3736
이 문제를 풀어볼 겁니다. 정말 그냥 단순히 이분 매칭. 끝입니다.
문제는 정점 개수가 최대 양쪽 9999개라, O(VE), 완전 이분 그래프일 시 O(V^3)으로 어려울 수 있다는 점.
이걸 호프크로프트 카프 알고리즘으로 풀어봅시다.
크흑... 사실 발굴만 안 된 꿀문제인지라 이 글을 쓸 당시까지는 저 혼자 푼 문제였는데, 눈물을 머금고 제 한 몸 희생하여 올립니다...
인증샷 ㅠㅠ 잠깐이지만 행복했어...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAX = 10000; const int INF = 1000000000; // A[i], B[i]: 그룹의 i번 정점과 매칭된 상대편 그룹 정점 번호 int N, A[MAX], B[MAX], dist[MAX]; // dist[i]: (A그룹의) i번 정점의 레벨(?) bool used[MAX]; // used: (A그룹의) 이 정점이 매칭에 속해 있는가? vector<int> adj[MAX]; // 호프크로프트 카프 전용 bfs 함수: A그룹의 각 정점에 레벨을 매김 void bfs(){ queue<int> Q; // 매칭에 안 속한 A그룹의 정점만 레벨 0인 채로 시작 for(int i=0; i<N; i++){ if(!used[i]){ dist[i] = 0; Q.push(i); } else dist[i] = INF; } // BFS를 통해 A그룹 정점에 0, 1, 2, 3, ... 의 레벨을 매김 while(!Q.empty()){ int a = Q.front(); Q.pop(); for(int b: adj[a]){ if(B[b] != -1 && dist[B[b]] == INF){ dist[B[b]] = dist[a] + 1; Q.push(B[b]); } } } } // 호프크로프트 카프 전용 dfs 함수: 새 매칭을 찾으면 true bool dfs(int a){ for(int b: adj[a]){ // 이분 매칭 코드와 상당히 유사하나, dist 배열에 대한 조건이 추가로 붙음 if(B[b] == -1 || dist[B[b]] == dist[a]+1 && dfs(B[b])){ // used 배열 값도 true가 됨 used[a] = true; A[a] = b; B[b] = a; return true; } } return false; } int main(){ while(scanf("%d", &N) > 0){ // 그래프 정보 입력받기 for(int i=0; i<N; i++){ int job, J; scanf("%d: (%d)", &job, &J); for(int j=0; j<J; j++){ int server; scanf("%d", &server); adj[job].push_back(server-N); } } // 호프크로프트 카프 알고리즘 int match = 0; fill(A, A+MAX, -1); fill(B, B+MAX, -1); while(1){ // 각 정점에 레벨을 매기고 시작 bfs(); // 이분 매칭과 비슷하게 A그룹 정점을 순회하며 매칭 증가량 찾음 int flow = 0; for(int i=0; i<N; i++) if(!used[i] && dfs(i)) flow++; // 더 이상 증가 경로를 못 찾으면 알고리즘 종료 if(flow == 0) break; // 찾았을 경우 반복 match += flow; } // 결과 출력 printf("%d\n", match); // 테스트 케이스가 여러 개이므로 초기화하는 부분 fill(used, used+MAX, false); for(int i=0; i<N; i++) adj[i].clear(); } } | cs |
일단 아까 관찰한 대로 A그룹 정점의 레벨은 항상 0, 2, 4, 6, ... 식이므로
그냥 0, 1, 2, 3, ...으로 매기는 식으로 코드를 최적화했고,
used라는 배열 또한 눈에 띕니다. 이건 매칭에 속해 있느냐는 값인데, 한 번 true가 되면 계속 true인 채로 남아 있습니다.
왜냐면, 맨 처음엔 길이 1짜리 증가경로를 찾는 것으로 매칭을 만들어갈 것이고, 그 이후엔 새로 찾는 증가 경로는 항상 양 끝점만 used가 false고 사이의 정점들은 used가 true일 테니까요.
지금까지 알고리즘을 관찰해 본 것처럼, 기존의 교차 경로를 찾아서 양끝에 새 정점을 붙이는 식으로 경로를 늘여서 매칭 크기를 증가시켜 왔으니까요.
그리고 매번 경로에 속한 간선들은 매칭에 속해있는 여부가 바뀌지만, 정점의 입장에서 보면 자신은 항상 어떤 매칭 간선에는 들어가 있기 때문에 한 번이라도 매칭에 속하게 된 정점은 앞으로 계속 매칭에 속하게 됩니다.
이 알고리즘의 시간복잡도가 왜 괴이하게도 O(E√V)인지는, 좀 어렵기도 하고 저도 잘 이해하지 못했습니다.
매 단계마다 항상 일정 개수의 새 매칭은 찾아낸다는 걸 의미하는 lemma가 있다고 합니다. 그 부등식에 루트식이 존재합니다.
2020년 9월 말, 이 문제에 걸려있던 1933번 문제 "등번호"가 이분매칭이 아닌 풀이가 발견되고 재채점되면서 글에서 삭제했습니다.
각 번호를 정점으로, 각 선수를 간선으로 생각하면 풀 수 있습니다. 더 큰 힌트를 주자면, 이렇게 그래프를 만들어 놓고, 한 컴포넌트 안에 정점 수보다 간선 수가 많은 경우가 불가능한 경우의 필요충분조건입니다.
추천 문제
3736번: System Engineer
위에서 설명한 문제입니다.
13166번: 범죄 파티 (★)
이 문제는 풀이법이 굉장히 많다고 합니다. 일단 출제진 의도는 2-SAT인데, 근처에선 DFS로 풀었단 사람도 나오고 뭐... 참고로 이 문제 역시 2016년 전대프연에 출연한 문제입니다.
그리고 출제진의 의도 중 하나가 이분 탐색 + 이분 매칭입니다.
파티 비용 제한이 k일 때 최대 매칭이 N인지를 판별하여, 이분 탐색으로 최소의 k를 찾는 것이죠.
문제는 N이 미친듯이 크기 때문에, 이분 매칭을 호프크로프트 카프 알고리즘으로 시행해야만 합니다.