[BOJ] #11376 열혈강호 2

https://www.acmicpc.net/problem/11376

---

최대 유량 (Max Flow) 의 특수한 형태인 문제들은 기존의 O(V * E^2)의 시간복잡도 대신 이분 매칭이라는 또다른 알고리즘을 통해 O(VE)의 시간으로 해결할 수 있다. 이번 문제 같은 경우가 딱 그런 경우인데, #11375번 열혈강호 문제의 업그레이드 버전이라 볼 수 있다. 사실 업그레이드도 아닌 것이,,, 그냥 한 정점에 대해 DFS와 visited 배열 초기화를 두번씩 돌려주면 된다.

대충 그려놨지만 그냥 보자...

다음 그림은 문제에서 주어진 입력값에 대한 이분 매칭 그래프를 그려본 것이다. 일할 사람을 1~5의 숫자로, 해야하는 일을 편의상 A~E까지의 알파벳으로 나타냈다. 또한 visited배열은 각 일에 대한 방문 여부, matched 배열은 해당 일을 누가 맡기로 했는지를 저장하게 된다. 최종적으로 해당 입력값에 대한 정답은 4가 되는데, 1번와 4번 사람이 각각 2개씩 일을 하면 최대 4개의 일을 할 수 있다. 

정답을 구하는 방법은 다음과 같다. 먼저 인접리스트 형태로 입력값을 받는다. 이후 하나의 정점씩 돌아가며 맡을 수 있는 일을 찾는데, 인접리스트 형태의 vector를 DFS 알고리즘을 통해 찾는다. 아예 배정이 되어있지 않으면 matched 배열에 그대로 넣어주면 되고, 만약 matched배열에 이미 값이 있더라도, (즉, 해당 일을 어떤 사람이 이미 맡고 있더라도) 해당 일을 담당하는 사람이 다른 일을 담당할 수는 없는지 다시 DFS를 통해 탐색하여 지금 선택된 사원이 최대한 일을 맡을 수 있게 한다. 만약 어떤 일을 누군가가 맡는것이 결정되었다면, DFS함수는 true를 리턴하고 total 값을 1 증가시켜준다. 모든 사원에 대한 탐색이 끝난 이후에 최종적인 total값을 출력하면 되는 것이다.

서두에서도 말했지만, #11375번 열혈강호 문제와 다른점이라 함은 한 정점에 대해 DFS 탐색을 두번씩 돌려줘야 한다는 점이다. 탐색을 거칠때마다 visited 배열 또한 초기화를 시켜주어야 하고. 이렇게 하는 이유는 문제에서 단순히 "각 직원은 자신이 할 수 있는 일들 중 최대 두 개의 일을 담당할 수 있고" 라는 조건을 붙여주었기 때문이다. 다른 이유는 없다.

문제에서 그려지는 그래프가 이분 그래프로 나뉠때, 최대 유량이 아닌 이분매칭 기법을 통해 문제를 더 빠른 시간안에 해결할 수 있다. 아마 최대 유량으로도 해결자체는 가능할 듯 한데, 시도해보진 않았다. 나중에 시간이 나면 한번 해보아도 재밌을듯 하다.

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 1001

using namespace std;

int matched[MAX];
bool visited[MAX];
vector<int> v[MAX];

bool DFS(int curr) {
    for (int next : v[curr]) {
        if (visited[next]) continue;

        visited[next] = true;

        if (matched[next] == 0 || DFS(matched[next])) {
            matched[next] = curr;
            return true;
        }
    }

    return false;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int N,M;
    cin >> N >> M;

    for (int target=1; target<=N; target++) {
        int size;
        cin >> size;

        while (size-->0) {
            int a;
            cin >> a;
            v[target].push_back(a);
        }
    }

    int total = 0;
    for (int target=1; target<=N; target++) {
        for (int i=0; i<2; i++) {
            fill(visited, visited+MAX, false);
            if (DFS(target)) total++;
        }
    }
    cout << total << '\n';

    return 0;
}

---

상당히 험난한 과정을 거쳤다...