BOJ 11376 : 열혈강호 2 [C++]

 

11376번: 열혈강호 2

 

이미 11375번 열혈강호 문제를 통해 이분 매칭을 알았기 때문에

이분 매칭을 사용해야겠다는 것은 금방 알 수 있었다.

 

하지만 이번 문제는 한 직원이 최대 2개의 일을 할 수 있다.

 

이걸 어떻게 처리해야 하나, 그냥 한 직원당 dfs를 두 번 돌리면 되나?라고 생각했는데...

 

맞다!

 

그냥 dfs 두 번 돌리면 된다

 

bool dfs(int worker) {
    visited[worker] = true;

    for (int job : jobs[worker]) {
        if (assigned_to[job] == 0 || (!visited[assigned_to[job]] && dfs(assigned_to[job]))) {
            assigned_to[job] = worker;
            return true;
        }
    }

    return false;
}

 

이분 매칭을 위한 dfs를 보면, dfs 전에 visited 배열을 초기화하더라도

dfs에 진입하는 순간 나(dfs에 진입할 때 파라미터로 넘긴 직원)는 방문 처리가 된다.

그렇기 때문에 for문 내의 조건문에서

내가(dfs에 진입할 때 파라미터로 넘긴 직원) 맡은 일은 dfs의 대상이 되지 않기 때문에,

두 번째 dfs에서 새로운 일을 할당받더라도 첫 번째 dfs를 통해 내가 맡은 일과는 다른 일을 할당받게 된다.

 

 

코드 

#include <iostream>
#include <cstring>
#include <vector>

int N, M;
bool visited[1001];		// dfs에서 i번 직원을 방문했는지
std::vector<int> jobs[1001]; 	// jobs[i] -> i번 직원이 할 수 있는 일 목록
int assigned_to[1001];		// assigned_to[i] -> i번 일이 어느 직원에게 할당되었는지

bool dfs(int worker) {
    visited[worker] = true;

    for (int job : jobs[worker]) {
        if (assigned_to[job] == 0 || (!visited[assigned_to[job]] && dfs(assigned_to[job]))) {
            assigned_to[job] = worker;
            return true;
        }
    }

    return false;
}

int main() {
    std::cin >> N >> M;

    int number_of_job, job;
    for (int i = 1; i < N + 1; i++) {
        std::cin >> number_of_job;
        for (int j = 0; j < number_of_job; j++) {
            std::cin >> job;
            jobs[i].push_back(job);
        }
    }

    int answer = 0;
    for (int i = 1; i < N + 1; i++) {
        std::memset(visited, false, sizeof(visited));
        if (dfs(i)) {
            answer++;
        }
        std::memset(visited, false, sizeof(visited));
        if (dfs(i)) {
            answer++;
        }
    }

    std::cout << answer << "\n";

    return 0;
}