[이분매칭/기초] 11375번 열혈 강호

클릭

위의 링크에 이분 매칭에 대해서 너무 잘 설명 되어 있기 때문에 한번 읽고 오는 것을 추천한다.

위의 문제는 해석해보면 다음과 같다. 1,2,3,4,5번 총 5명의 사람이 있고 1,2,3,4,5의 총 5개의 작업이 존재한다. 각각의 작업과 각각의 사람이 1:1로 매칭되어 어떤 한 사람이 한 작업을 처리할수 있게끔 매칭하는것이 목적이다.

예를 들어 위의 예제에서

1번 사람은 1,2번 작업을 처리할수 있고

2번 사람은 1번 작업만을 처리할수 있다고 예제 입력이 되었다.

이 상황에서 1번사람이 2번작업을 처리하고 2번사람이 1번작업을 처리하게끔 매칭 시켜주면 된다.

이분 매칭이라는 의미는 어떤 그래프에서 노드들의 그룹을 두개로 나눴을때 각 그룹내에서는 엣지가 생기지 않고 그룹끼리의 엣지만 존재하게끔 노드를 두개의 그룹으로 나누는 것이다.

그래서 매칭 되는 작업과 사람의 숫자를 최대로 늘리기 위한 방법에 대한 알고리즘이다.

풀이방법은 다음과 같다.

우선 어떤 작업에 대해서 그 작업을 처리해줄 사람의 번호를 저장할 배열이 하나 필요하다

이것은 match[1001]이라는 배열이다. 사람이 1000명까지 존재할수 있기 때문에 1001개로 선언했다.

예를 들어 match[2] = 1; 이라면 2번 작업에 대해 1번사람이 처리 하겠다는 의미이다. 즉 왼쪽 그룹의 1번과 오른쪽 그룹의 2번이 매칭 되었다는 의미이다.

또한 dfs중복실행을 막기 위해서 visited배열이 필요하다.(이것은 알고리즘을 보면 왜 필요한지 알게 될것이다.)

이렇게 준비를 해놓고

각 사람의 번호에 대해서(1~5번) dfs를 1,2,3,4,5번 정점에 대해서 각각 돌리면 된다.

돌릴때마다 visited배열은 0으로 초기화를 해주어야 한다. 왜냐면 하나의 사람을 어떤 작업에 매칭 시키는 작업은 독립적인 단위이기 때문이다.

먼저 1번 사람에 대해서 작업을 매칭시키는 dfs가 실행 되었을때,

1번과 연결된 모든 정점에 대해서 검사를 시작한다. 예를 들어 위에 예제에서 1번 사람과 1,2번 작업이 연결 되어 있다.

1번 작업에 가서 이 작업이 이미 누군가에게 할당 되었는가를 확인하기 위해서 match[1]을 확인해보고 이게 0이라면 아직 작업이 어떤 사람에게 위임되지 않았다는 의미이기 때문에 그냥 바로 1번 사람과 1번작업을 매칭 시키면된다.

그리고 나서 visited배열을 모두 0으로 초기화해주고 2번 사람에 대해서도 dfs를 돌리기 시작한다. 2번 사람은 1번 작업만 처리할 수 있다. 그래서 2번 사람에 대해서 dfs를 돌리게 되면 1번작업이 이미 1번사람에게 매칭 되어 있으므로 1번 사람이 재귀적으로 다른 노드와 매칭 되게끔 해준다음 자신(2번노드)이 1번 작업과 연결을 해버린다.

만약에 1번 사람이 1번 작업 외에 다른 작업에 매칭이 불가능 하다면 2번 사람은 1번작업에 대한 매칭을 포기하고 그 다음 작업을 처리할수 있는지 확인하지만, 그런 작업이 없으므로 그냥 매칭이 실패한것으로 친다.

이런식으로 반복하여 동작하고, 최종적으로 마지막에 match배열을 살펴보면 각 i번째 작업에 매칭된 사람의 번호가 저장되어 있으므로 각 작업이 어떤 사람에게 할당 되었는지 출력할수 있게 되고 몇개의 작업이 처리될수 있는지도 체크 할 수 있다.

코드

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
int n, m;//n은 직원의수 m은 일의 개수
int match[1001]; //i번째 작업과 매칭된 match[i]번째 사람.
bool visited[1001];//i번째 사람을 이미 방문했는가. 중복 방문을 피하기 위해서 존재함.
vector<vector<int>> v(1001); //각 사람이 할 수 있는 작업을 저장하기 위한 2차원 벡터
 
bool dfs(int here) //here는 현재 사람의 번호
{
    if (visited[here]) return 0;
    //그 사람을 이미 방문했다는 것의 의미는 그 사람과 연결된 작업에 대해 dfs를 돌리고 있거나 이미 다 돌렸다는 의미이다.
    //따라서 한번더 dfs를 돌릴 필요가 없으므로 return 0;을 시켜버리면 된다.
    visited[here] = 1;
 
    for (int i = 0; i < v[here].size(); i++) {
        int work = v[here][i]; //work는 here번째 사람에게 연결된 작업의 번호중 하나임.
        if (!match[work] || dfs(match[work]))//그 작업에 연결된 사람이 없는경우 또는 현재 작업에 연결된 사람에게 다른 작업을 매칭 시킬수 있는 경우.
        {
            match[work] = here; //그 작업을 현재 사람에게 매칭
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int j; cin >> j;
        for (int k = 1; k <= j; k++) {
            int temp; cin >> temp;
            v[i].push_back(temp);
        }
    } //초기 입력 세팅
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i))
            cnt++;
    }
    cout << cnt << endl;
 
    return 0;
}