[BOJ] #14433 한조 대기 중

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

---

상당히 가슴아픈 문제이다. 양 팀에 트롤짓을 하는 팀원이 무조건 있는데, 트롤링을 하는 팀원이 더 적은쪽이 이겼다는 문구를 띄워야 한다. 한쪽 집합은 게임에 임하는 플레이어의 집합, 다른 한쪽은 각 팀별 트롤픽 집합을 둔 뒤에 이분 매칭을 통해 어떤 쪽이 매칭이 더 적은지 판별하면 되는 문제이다. 사실 플래티넘4 난이도의 문제라고 하기엔 알고리즘 딱 하나만을 써서 푸는 문제여서 그다지 어렵진 않았다. 이분 매칭 알고리즘을 잘 적용할 수 있으면 바로 풀 수 있는 문제인 듯.

다음 그림을 보자. 기본으로 주어져있는 입력 예시를 그대로 이분그래프 형태로 나타낸 것이다.

파란색으로 쓴것이 팀원의 숫자이고, 빨간색이 각 팀별 트롤픽의 수인 K1 과 K2 이다. 각 그래프 마다 이분매칭을 진행하며 매칭되는 갯수를 세아리면 된다. 지금으로서는 첫번째 팀의 트롤픽이 4개, 두번째 팀의 트롤픽이 1개로 트롤픽이 더 적은 두번째 팀이 이기게 된다. 

코드 설계는 동일한 이분매칭 DFS 함수에 인자로 vector 배열 (여기서는 이분 그래프) 을 넘겨서 Pass by Reference 형식으로 설계하였다. 같은 이분 매칭 알고리즘을 서로 다른 두개의 그래프를 상대로 각 한번씩 총 두번 수행한다. 이때, 각 수행마다 매칭된 간선을 담는 matched 배열을 초기화 해주어야 함에 유의하자.

---

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

#define MAX 301

using namespace std;

int N,M,K1,K2;
int matched[MAX];
bool visited[MAX];
vector<int> V1[MAX], V2[MAX];

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

        visited[next] = true;

        if (!matched[next] || DFS(v, matched[next])) {
            matched[next] = curr;
            return true;
        }
    }
    return false;
}

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

    cin >> N >> M >> K1 >> K2;

    int a,b;
    for (int i=0; i<K1; i++) {
        cin >> a >> b;
        V1[a].push_back(b);
    }
    for (int i=0; i<K2; i++) {
        cin >> a >> b;
        V2[a].push_back(b);
    }

    int total1=0, total2=0;
    for (int target=1; target<=N; target++) {
        fill(visited, visited+MAX, false);
        if (DFS(V1, target)) total1++;
    }
    fill(matched, matched+MAX, 0);
    for (int target=1; target<=N; target++) {
        fill(visited, visited+MAX, false);
        if (DFS(V2, target)) total2++;
    }

    total1 < total2 ? cout << "네 다음 힐딱이\n" : cout << "그만 알아보자\n";

    return 0;
}