[C++] 백준 11375번 - 열혈강호

 

📖 문제

 

📋 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, M, ans;
bool visited[1001];
int bm[1001]; // Bipartite Matching
vector<vector<int>> node(1001);

bool DFS(int personNum)
{
    if (visited[personNum]) // 이미 방문된 정점은 매칭 불가
        return false;
    visited[personNum] = true;
    for (int i = 0; i < node[personNum].size(); i++)
    {
        int workNum = node[personNum][i];
        // 해당 work가 매칭되어있지 않거나
        // 해당 work에 매칭되어 있는 사람이 다른 work와 매칭될 수 있을 때
        if (bm[workNum] == 0 || DFS(bm[workNum]))
        {
            bm[workNum] = personNum; // person <-> work 매칭
            return true;
        }
    }
    return false;
}

void initVisited()
{
    for (int i = 1; i <= N; i++)
    {
        visited[i] = false;
    }
}

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

    for (int i = 1; i <= N; i++)
    {
        int ea, workNum; // 일의 개수, 번호
        cin >> ea;
        for (int j = 1; j <= ea; j++)
        {
            cin >> workNum;
            node[i].push_back(workNum);
        }
    }

    for (int i = 1; i <= N; i++)
    {
        initVisited(); // 방문기록 초기화
        if (DFS(i))
            ans++;
    }

    cout << ans;
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

전형적인 이분 매칭 문제입니다.

 

잠시만요 이분 매칭이 뭐죠..?

이분 매칭(Bipartite Matching)이란?

두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 한쪽 그룹을 A, 다른 쪽 그룹을 B라고 할 때 모든 경로의 방향이 A->B인 그래프의 최대 유량을 구하는 것을 이분 매칭이라고 합니다.

이러한 이분 매칭을 통해서 구할 수 있는 것을 최대 매칭 수 인데, 문제에서 요구하는 직원들이 담당할 수 있는 일의 최대 개수를 이분 매칭을 통해서 알아낼 수 있습니다.

 

int N, M, ans;
bool visited[1001];
int bm[1001]; // Bipartite Matching
vector<vector<int>> node(1001);

visited 배열은 정점(직원의 번호)의 방문을 기록하는 배열
bm 배열은 해당 일을 담당하는 직원의 번호를 기록하는 배열
(ex : bm[3]=1의 의미는 3번 일감을 1번 직원이 담당하고 있다는 의미입니다.)

 

bool DFS(int personNum)
{
    if (visited[personNum]) // 이미 방문된 정점은 매칭 불가
        return false;
    visited[personNum] = true; // 방문 표시
    for (int i = 0; i < node[personNum].size(); i++)
    {
        int workNum = node[personNum][i];
        // 해당 work가 매칭되어있지 않거나
        // 해당 work에 매칭되어 있는 사람이 다른 work와 매칭될 수 있을 때
        if (bm[workNum] == 0 || DFS(bm[workNum]))
        {
            bm[workNum] = personNum; // person <-> work 매칭
            return true;
        }
    }
    return false;
}

DFS 코드를 살펴봤을 때 전체적으로 보면 이미 방문한 노드이거나 일이 매칭이 안되었을 때 false를 return,
일이 매칭 된다면 true를 return 합니다.

for문으로 해당 직원이 할 수 있는 일의 목록을 나열하고 

1. 해당 일을 담당하는 직원이 없는지? (  bm[workNum] == 0  )
2. 해당 일을 담당하는 직원이 혹시.. 다른 일에 매칭 될 수 있는지? (  DFS(bm[workNum])  )

확인을 하고 1, 2번 경우 중 적어도 하나에 해당된다면 현재 직원(personNum)을 일(workNum)에 매칭 시키고 true를 return 합니다.

 

void initVisited()
{
    for (int i = 1; i <= N; i++)
    {
        visited[i] = false;
    }
}

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

    for (int i = 1; i <= N; i++)
    {
        int ea, workNum; // 일의 개수, 번호
        cin >> ea;
        for (int j = 1; j <= ea; j++)
        {
            cin >> workNum;
            node[i].push_back(workNum);
        }
    }

    for (int i = 1; i <= N; i++)
    {
        initVisited(); // 방문기록 초기화
        if (DFS(i))
            ans++;
    }

    cout << ans;
}

위에서 DFS는 일이 매칭이 되는 경우에 true를 return 한다고 설명드렸습니다. 매칭이 될 때마다 ans값을 +1 하여서 출력하면 정답을 출력할 수 있습니다.

 

 

이분 매칭에 대해 간단한 그림으로 설명드리자면

1번 직원은 일 1,2,3번이 가능하고 현재 1번 일이 매칭 되어있지 않으므로
1번 직원과 1번 일을 매칭 시킵니다.

 

2번 직원 : 1 번님! 제가 1번 일 처리할 테니 다른 일 처리하실래요..?
1번 직원 : 어.... 잠시만요..! 저 2번 일도 처리 가능하니 2번 일 담당할게요. 그럼 2 번님이 1번 일 맡으셔요! 

이분 매칭 자체가 굴러온 돌이 박힌 돌을 빼내는 형식입니다. ㅎㅎ...
코드상으로는 DFS(bm[1])을 호출하여 1번 직원이 다른 일을 탐색하게 되고 2번 일에 매칭 되어 true를 리턴합니다.
그리고 bm[2] = 1로 2번 직원을 1번 일에 매칭 시키게 됩니다. 

 

3번 직원 : 1 번님.. 죄송합니다만.. 2번 일 제가 처리해도 될까요..?
1번 직원 : ....... 잠시만요;; 3번 일은 제가 할 수 있을 것 같네요. 그럼 3번 일 맡겠습니다 ㅜ.ㅜ

이번에는 3번 직원이 2번 일을 선택하기 위해서 1번 직원에게 다른 일을 맡는 것이 가능한지(DFS(bm[2]) 호출) 살펴보고 1번 직원이 다행히도 3번 일에 매칭 되어 3번 직원은 2번 일에 매칭 되게 됩니다. (bm[2] = 3)

 

간단하게 이분 매칭은 이러한 프로세스입니다. 핵심은
"제가 이 일 처리할 테니 님 다른 일 가능한지 한번 알아보시고 불가능하시면 제가 다른 일 알아볼게요" ...??
인 것 같습니다. 😂

 

 

 

🔗 링크

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

11375번: 열혈강호