돌멩이 제거 (feat. 백준, 1867번)

돌멩이 제거
https://www.acmicpc.net/problem/1867

1867번: 돌멩이 제거

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int N, K, check[501];   // 인덱스는 행
vector<int> arr[501];   // 인덱스는 행, 값은 열
bool visit[501];       // 인덱스는 행
bool dfs(register int n){
    for(auto& v : arr[n]){
        if(visit[v])
            continue;
        visit[v] = true;
        if(!check[v] || dfs(check[v])){
            check[v] = n;
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int ans = 0;
    cin >> N >> K;
    for(register int k = 1, a, b; k <= K; ++k){
        cin >> a >> b, arr[a].push_back(b);
    }
    for(register int n = 1; n <= N; ++n){
        memset(visit, false, sizeof(visit));
        if(dfs(n))
            ++ans;
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

이전 "열혈강호" 와 유사한 문제입니다.

열혈강호 (feat. 백준, 11375번)

 

오늘은 이분매칭과 관련된 문제를 세개 풀어 보았습니다.

이분매칭 문제의 유형과 풀이법을 조금이나마 익힐 수 있었네요.