[BOJ 11377] 열혈강호3

백준 문제 링크

🔍 문제 분석

• 대표적인 이분 매칭 문제로 N명 중 최대 K명은 최대 2개의 일을 담당할 수 있다는 차이점이 있다.
• 본 문제는 다음과 같은 과정으로 풀이한다.
  1. 일반적인 이분 매칭을 수행한다.
  2. 이분 매칭을 한 번 더 수행하며, 성공한 매칭의 횟수가 K가 되면 종료한다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 1'000;

int N, M, K, match[MAX + 1], is_visited[MAX + 1];
vi graph[MAX + 1];

bool dfs(int node) {
    for (auto next : graph[node]) {
        if (is_visited[next]) continue;
        is_visited[next] = true;
        if (match[next] == node) continue;
        if (match[next] == 0 || dfs(match[next])) {
            match[next] = node;
            return true;
        }
    }
    return false;
}

int main() {
    fastio;

    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i) {
        int n;
        cin >> n;
        while (n--) {
            int m;
            cin >> m;
            graph[i].push_back(m);
        }
    }

    for (int i = 1; i <= N; ++i) {
        memset(is_visited, 0, sizeof(is_visited));
        dfs(i);
    }

    for (int i = 1; i <= N; ++i) {
        if (!K) break;
        memset(is_visited, 0, sizeof(is_visited));
        if (dfs(i)) K--;
    }

    int ans = 0;
    for (int i = 1; i <= M; ++i) {
        ans += !!match[i];
    }
    cout << ans;
}

📝 코드 설명

if (match[next] == node) continue;

• 두번째 이분 매칭에서 자기 자신이 첫번째 이분 매칭때 담당한 일에 대해서 재귀 호출을 하지 않도록 주의한다.

🔧 트러블 슈팅

📚 참고자료