[BOJ 백준] 1867번 돌멩이 제거

문제

BOJ number : https://www.acmicpc.net/problem/1867

1867번: 돌멩이 제거

접근

이분 매칭(Bipartite Matching)을 이용하여 문제를 해결하였다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, k, ans = 0, visit[510], matchNum[510] = {0};
vector<int> graph[510];

int dfs(int n){
    for (int i : graph[n]) {
        if (!visit[i]) {
            visit[i] = 1;
            if (!matchNum[i] || dfs(matchNum[i])) {
                matchNum[i] = n;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> k;

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) 
            visit[j] = 0;
        ans += dfs(i);
    }
    
    cout << ans;

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study