BOJ 1867 돌맹이 제거

돌맹이 제거
(http://boj.kr/1867)

요즘 기초적인 이분 매칭 문제들을 보고 있는데, 이분 매칭이라는 분류를 안 보면 알아차리기 힘들 것 같다. 그냥 왠지 안 풀리면 의심해봐야겠다.

이 문제에서는 \(i\)행 \(j\)열에 돌맹이가 있다면, \(i\)행을 청소하거나 \(j\)열을 청소해야 한다. 즉, 둘 중 하나를 선택해야 한다.
그래프는 행을 청소하는 경우, 열을 청소하는 경우로 나뉘고, \(i\)행 \(j\)열에 돌맹이가 있다면 \(i\)행과 \(j\)열을 이어준다.
그리고 \(i\)행에서 \(j\)열을 매칭하는 것은 \(i\)행을 청소하거나 \(j\)열을 청소하는 것이다. 만약 매칭할 수 있는게 여러가지라면 \(i\)행을 청소할 것이고, 한 가지라면 \(j\)열을 청소하게 될 것이다.
그러면 다른 행에서 \(j\)열을 청소하려 할 때 \(i\)행에서 비킬 수 있다는 것은 그 행이나 \(j\)열에서도 청소를 해야한다는 뜻이므로 최대 매칭과 같아진다.

#include <bits/stdc++.h>
 
using namespace std;
 
pair<int, int> roc[501];
vector<int> gph[501];
bool chk[501];
int con[501];
 
bool f(int now) {
    if (chk[now])
        return false;
    chk[now] = true;
 
    for (int nxt : gph[now])
        if (con[nxt] == 0 || f(con[nxt])) {
            con[nxt] = now;
 
            return true;
        }
    return false;
}
 
int main() {
    int n, k, cnt = 0;
 
    scanf("%d %d", &n, &k);
 
    for (int i = 1;i <= k;++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        gph[u].push_back(v);
    }
 
    for (int i = 1;i <= n;++i) {
        memset(chk, false, sizeof(chk));
        if (f(i))
            cnt++;
    }
 
    printf("%d", cnt);
 
    return 0;
}