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

열혈강호
https://www.acmicpc.net/problem/11375

11375번: 열혈강호

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int N, M, ans, task[1001];    // 인덱스는 일, 값은 담당 직원 번호
bool arr[1001][1001], visit[1001];
bool dfs(register int n){
    for(register int m = 1; m <= M; ++m){
        if(!arr[n][m] || visit[m])
            continue;
        visit[m] = true;
        if(!task[m] || dfs(task[m])){
            task[m] = n;
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(task, 0, sizeof(task));
    memset(arr, false, sizeof(arr));
    cin >> N >> M;
    for(register int n = 1, c; n <= N; ++n){
        cin >> c;
        for(register int i = 1, m; i <= c; ++i)
            cin >> m, arr[n][m] = true;
    }
    ans = 0;
    for(register int n = 1; n <= N; ++n){
        memset(visit, false, sizeof(visit));
        if(dfs(n))
            ++ans;
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

1. 1번 직원이 a와 b의 일 모두를 할 수 있다고 가정해보겠습니다. a가 순서가 앞순서이니 1번 직원은 a 일을 담당합니다.
2. 2번 직원이 a 일을 할 수 있다고 가정해보겠습니다. 1번 직원이 b 일을 담당해준다면 2번 직원이 a 일을 담당할 수 있으므로 효율적일껍니다. 왜냐하면 한명의 직원은 하나의 일만 가져가야 하니까요.
3. 따라서 2번 직원은 a 일을 담당하는 직원에게 'a 일은 내가 할테니까 당신은 다른 일을 하세요.' 라고  백트래킹을 통해 알려줍니다. (13번째줄의 dfs 재귀호출 및 visit의 초기화를 눈여겨보세요.)