141. Bipartite Matching

플로우 문제를 풀다 보면 특수한 형태의 그래프가 자주 등장하는 것을 알 수 있다. 아래의 그래프를 보자.

소스에서 첫 번째 그룹의 정점들로 가는 간선들이 있고, 첫 번째 그룹의 정점들에서 두 번째 그룹의 정점들로 가는 간선이 있고, 두 번째 그룹의 정점들에서 싱크로 가는 간선이 있다. 각 간선의 용량은 전부 $1$이다.

 

위 그래프에서 소스와 싱크를 없애고 간선의 방향 표시도 없애면 아래와 같은 이분 그래프가 된다.

간선의 용량이 전부 $1$이므로, 이 그래프에서 최대 유량을 구하는 문제는 첫 번째 그룹에 속하는 정점들과 두 번째 그룹에 속하는 정점들 간의 최대 매칭(Maximum Matching)의 크기를 찾는 문제로 생각할 수 있다. 앞서 소스와 싱크에 연결된 간선들의 용량도 전부 $1$이었으므로 각각의 간선뿐 아니라 정점들도 최대 한 번밖에 선택하지 못한다는 것에 주의하자. 아래와 같이 정점을 연결하면 이 그래프의 최대 매칭의 크기는 $3$이다.

이렇게 이분 그래프에서 최대 매칭의 크기를 구하는 것을 이분 매칭(Bipartite Matching)이라고 한다. 이 그래프에서 포드-풀커슨 알고리즘으로 최대 매칭의 크기를 구하면 $w \le n$이므로 시간복잡도가 $O(nm)$이 되며, 이때 최대 매칭의 크기를 구하는 과정을 더 단순화한 것이 일반적으로 이분 매칭 문제를 해결하는 알고리즘으로 알려져 있다.

---

이분 그래프에서 최대 매칭을 구하는 알고리즘은 다음과 같이 작동한다.

    1. 첫 번째 그룹에서 정점 하나를 고른다.

    2. 그 정점과 연결된 두 번째 그룹의 정점 중 아직 매칭이 안 된 정점이 있다면 그중 하나를 골라서 매칭한다.

    3. 그런 정점이 없는 경우, 첫 번째 그룹에서 고른 정점을 연결된 정점 중 하나와 매칭하고 매칭된 두 번째 그룹의 정점의 원래 매칭을 끊는다. 그러면 그 정점과 연결된 첫 번째 그룹의 정점의 매칭도 같이 끊어지는데, 이 정점의 매칭을 앞과 같은 방법으로 시도한다.

    4. 이 과정을 반복해서 매칭을 성공했다면 최대 매칭의 수가 $1$ 증가한다.

    5. 첫 번째 그룹의 각 정점에 대해 위의 과정을 반복한다.

 

위의 그래프에서 최대 매칭을 구하자. 다양한 경우를 설명하기 위해 그룹의 정점을 확인하는 순서를 섞었다. 먼저 정점 $\text{B}$를 확인하고, $\text{B}$와 연결된 정점 중 $\text{F}$와 매칭이 되었다고 하자.

다음으로 정점 $\text{C}$를 확인하고, $\text{C}$와 연결된 정점 중 $\text{E}$와 매칭이 되었다고 하자.

다음으로 정점 $\text{A}$를 확인한다. $\text{A}$와 연결된 정점은 $\text{F}$인데, $\text{F}$가 $\text{B}$와 매칭되었으므로 임시로 $\text{A}$와 $\text{F}$를 매칭하고 $\text{B}$를 다른 정점과 매칭하는 것을 시도한다.

$\text{B}$와 연결된 다른 정점은 $\text{E}$가 있다. $\text{E}$는 $\text{C}$와 매칭되었으므로 임시로 $\text{B}$와 $\text{E}$를 매칭하고 $\text{C}$를 다른 정점과 매칭하는 것을 시도한다.

$\text{C}$와 연결된 다른 정점은 $\text{G}$가 있다. $\text{G}$는 아직 매칭되지 않았으므로 $\text{C}$와 $\text{G}$를 매칭한다. 또한 앞에서 임시로 매칭한 두 쌍도 정식으로 매칭한 것이 된다.

이제 정점 $\text{D}$를 확인할 차례이다. $\text{D}$와 연결된 정점은 $\text{F}$이고, $\text{F}$는 $\text{A}$와 매칭되어 있다. 따라서 $\text{A}$를 다른 정점과 매칭하는 것을 시도하는데, 다른 정점이 없으므로 매칭에 실패한다. 이 경우 임시로 매칭한 쌍들이 전부 끊어지고 원래 상태가 유지된다.

첫 번째 그룹의 모든 정점을 확인했으므로 실행을 종료한다. 구한 최대 매칭의 크기는 $3$이다.

---

 

구현은 다음과 같다. 첫 번째 그룹의 정점 수가 $n1$, 두 번째 그룹의 정점 수가 $n2$이고 $\text{b1}$과 $\text{b2}$는 두 그룹의 정점들이 각각 반대쪽 그룹의 어떤 정점과 매칭되어 있는지를 저장한다. $\text{vi}[i]$는 첫 번째 그룹의 $i$번 정점이 임시로 매칭된 상태인지를 체크한다.

#import<bits/stdc++.h>
using namespace std;
int s, b1[1005], b2[1005], vi[1005];
vector<int>e[1005];
int match(int u)
{
    vi[u] = 1;
    for(auto &v: e[u])
    {
        int p = b2[v];
        if(!p || !vi[p] && match(p))
        {
            b1[u] = v;
            b2[v] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int m, n1, n2, x, y;
    cin >> n1 >> n2 >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
    }
    for(int i = 1; i <= n1; i++)
    {
        fill(vi + 1, vi + n1 + 1, 0);
        s += match(i);
    }
}

실행이 끝나면 $s$에는 최대 매칭의 크기가 저장되고, 매칭의 정보가 $\text{b1}$, $\text{b2}$에 저장된다.

 

[연습문제]

 

BOJ 2188. 축사 배정 (Platinum IV)

소와 축사를 각 그룹으로 간주하여 최대 매칭의 크기를 구한다.

 

BOJ 11375. 열혈강호 (Platinum IV)

직원과 일을 각 그룹으로 간주하여 최대 매칭의 크기를 구한다.

 

BOJ 11376. 열혈강호 2 (Platinum IV)

각 직원이 일을 $2$개까지 할 수 있으므로, 직원을 나타내는 정점들 각각을 둘로 분할한 다음 최대 매칭의 크기를 구하면 된다.

 

BOJ 11377. 열혈강호 3 (Platinum III)

처음에는 각 직원이 일을 하나만 할 수 있는 것으로 간주하여 최대 매칭을 구하고, 그 상태에서 직원이 할 수 있는 두 번째 일을 나타내는 정점들을 추가하여 매칭을 더 찾는데, 여기서는 최대 $K$개의 매칭만 찾는다.

 

BOJ 1671. 상어의 저녁식사 (Platinum III)

이번에는 상어를 나타내는 그룹을 두 개 만든다. $A$ 상어에서 $B$ 상어로 가는 간선은 $A$ 상어가 $B$ 상어를 잡아먹을 수 있다는 의미이다. 또한 첫 번째 그룹에는 각 상어를 나타내는 정점이 $2$개씩 있어야 한다. 이제 이 그래프에서 최대 매칭의 크기를 구하면 잡아먹히는 상어 수의 최댓값이 구해지므로 문제를 풀 수 있다.

 

BOJ 1017. 소수 쌍 (Platinum III)

두 수의 합이 소수가 되려면 홀수와 짝수를 더해야 한다(모든 수가 다르기 때문에 $1 + 1 = 2$라는 예외는 발생하지 않음). 따라서 리스트에 존재하는 수를 홀수와 짝수로 나누어 두 수의 합이 소수인 경우 간선을 추가한다. 이제 첫 번째 수와 $i$번째 수를 나타내는 정점을 그래프에서 제거했을 때 모든 정점을 매칭할 수 있는 경우 $i$번째 수를 출력하면 된다. $(2 \le i \le N)$

 

BOJ 9525. 룩 배치하기 (Platinum III)

그리드를 이분 그래프로 변형해서 최대 매칭을 찾는 문제이다. 먼저 각 행마다 룩이 한 번에 이동할 수 있는 구간들을 묶어서 첫 번째 그룹으로 하고, 각 열마다 같은 과정을 반복해서 두 번째 그룹으로 한다. 그러면 각각의 칸을 포함하는 구간을 나타내는 정점은 각 그룹에 하나씩 존재하며, 이 정점들 사이에 전부 간선을 추가한다. 이제 최대 매칭의 크기를 구한다.

 

BOJ 2570. 비숍2 (Platinum II)

룩이 비숍으로 바뀌었다. 풀이는 9525번과 비슷하다.

 

→ solved.ac tag: bipartite_matching