[1574] 룩 어택

https://www.acmicpc.net/problem/1574

1574번: 룩 어택

<문제>

board[i][j]가 빈칸이 아니라면, i->j를 연결해준다.

이분 그래프중 한쪽은 행이고 한쪽을 열로 두었을때 최대매칭수를 찾으면 그것이 곧 답이되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, k, d[303];
bool check[303];
int board[303][303];
vector<int> adj[303];
bool f(int cur) {
    for (auto& next : adj[cur]) {
        if (check[next] == true) continue;
        check[next] = true;
        if (d[next] == 0 || f(d[next]) == true) {
            d[next] = cur;
            return true;
        }
    }
    return false;
}
int main(void) {
    int i, j;
    cin >> n >> m >> k;
    for (i = 0; i < k; i++) {
        int A, B;
        cin >> A >> B;
        board[A][B] = -1;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (board[i][j] != -1) {
                adj[i].push_back(j);
            }
        }
    }
    int ans = 0;
    for (i = 1; i <= n; i++) {
        memset(check, 0, sizeof(check));
        if (f(i) == true) ans++;
    }
    cout << ans;
    return 0;
}