문제 43
이분 매칭 1
왼쪽 그룹에는 $1$번부터 $N$번까지, 오른쪽 그룹에는 $1$번부터 $M$번까지 번호가 붙은 정점이 있다.
서로 다른 그룹에 속한 두 정점을 연결하는 $K$개의 간선이 주어진다.
서로 끝점을 공유하지 않도록 간선을 선택할 때 선택할 수 있는 간선 개수의 최댓값을 구하라.
입력
첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1 \le N, M \le 1\,000; 0 \le K \le 10\,000)$
두 번째 줄부터 $K$개의 줄에 걸쳐 각 간선이 연결하는 왼쪽 그룹과 오른쪽 그룹의 정점 번호를 의미하는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다. $(1 \le a \le N; 1 \le b \le M)$
같은 두 정점을 연결하는 간선은 두 번 이상 주어지지 않는다.
출력
선택할 수 있는 간선 개수의 최댓값을 출력한다.
예제 입력 1
4 4 6 1 1 1 2 1 4 2 3 3 1 4 3
예제 출력 1
3
예제 입력 2
3 4 0
예제 출력 2
0
공식 해설
왼쪽 정점마다 간선 전체를 한 번 정도 탐색해도 $O(NK)$이며 주어진 제한에서 충분하다. 새 정점을 연결할 때 기존 짝을 재배치할 수 있는지를 탐색하자.
오른쪽 정점이 이미 다른 왼쪽 정점과 연결되어 있어도, 기존 짝을 다른 곳으로 옮길 수 있다면 새 간선을 선택할 수 있다. 이 재배치를 DFS로 찾는다.
왼쪽 정점 $u$에서 이웃 $v$를 확인한다. $v$의 짝이 없으면 $u$와 연결한다. 짝 $w$가 있다면 먼저 $w$를 다른 오른쪽 정점에 연결할 수 있는지 탐색하고, 성공하면 빈 자리가 된 $v$를 $u$에 연결한다. 한 탐색에서 방문한 왼쪽 정점을 다시 방문하지 않도록 표시한다.
성공한 탐색은 미선택 간선과 선택 간선이 번갈아 나오는 증강 경로이다. 경로의 선택 여부를 뒤집으면 내부 정점의 연결은 유지되고 양 끝이 새로 연결되어 매칭 크기가 $1$ 증가한다.
왼쪽 정점을 하나씩 추가하며 이 탐색을 수행한다. 이전 정점들에 대한 매칭이 최대라면 더 큰 매칭을 만들 증강 경로는 새 정점에서 시작해야 한다. 두 매칭의 서로 다른 간선들을 비교하면, 크기를 늘릴 수 있을 때 이런 경로가 반드시 존재한다. 따라서 성공 횟수가 최대 매칭 크기이다.
방문 배열에는 탐색 번호를 기록하면 매번 배열 전체를 초기화할 필요가 없다. 시간복잡도는 $O(N(K+1)+M)$, 공간복잡도는 $O(N+M+K)$이다.
구현 · 언어별 풀이
C++ 구현
오른쪽 정점의 짝을 저장하는 vector<int>를 $-1$로 초기화한다. 탐색 함수는 짝이 없거나 기존 짝을 옮길 수 있을 때 성공을 반환한다. 방문 배열에는 탐색 번호를 저장하여 매번 전체를 지우지 않는다.
C 구현
오른쪽 정점의 매칭 상대를 int 배열에 둔다. 왼쪽 정점마다 새 방문 표식으로 증가 경로 DFS를 수행한다. 실패한 시도에서 남은 방문 표식을 다음 시도와 공유하지 않는다.
Python 구현
인접 리스트와 오른쪽 match 배열을 사용한다. DFS 깊이가 1000에 이를 수 있어 기본 재귀 한도에 의존하지 말고 명시적 탐색 스택과 경로를 두어 증가 경로를 복원할 수 있다. 시도별 방문 표식을 갱신한다.
Java 구현
int[] match와 방문 세대 번호를 사용한다. 증가 경로를 찾으면 복귀하면서 매칭을 바꾼다. 깊이가 최대 N에 이르므로 입력 최대 크기에서는 반복 DFS로 재귀 스택 의존을 없앨 수 있다.
Rust 구현
match와 seen을 Vec에 저장하고 DFS에 전달한다. 이웃 번호를 복사한 뒤 재귀 호출하면 인접 목록의 borrow와 매칭 변경을 분리할 수 있다. 각 시작 정점마다 방문 세대를 새로 부여한다.
JavaScript 구현
오른쪽 정점의 짝과 방문 탐색 번호를 Int32Array에 둔다. 각 왼쪽 정점에서 새 탐색 번호로 증강 경로를 찾고, 성공한 경로에서만 짝을 교체한다.
재귀를 피하려면 탐색 스택에 왼쪽 정점과 다음 이웃 위치를, 새 왼쪽 정점에는 직전에 선택한 오른쪽 정점을 기록한다. 빈 오른쪽 정점을 찾으면 그 경로를 거슬러 짝을 바꾼다. 이미 연결된 짝을 먼저 지우고 탐색하면 실패 시 매칭을 잃을 수 있으므로 성공한 뒤 반영한다. 결과는 최대 $1\,000$이라 Number로 충분하다.