안녕하세요! 오늘은 백준의 Platinum_III 난이도 문제인 "System Engineer"를 함께 풀어보는 시간을 갖겠습니다. 이 문제는 **이분 매칭(Bipartite Matching)** 알고리즘을 이용하여 해결할 수 있는 문제입니다.

백준 3736: System Engineer

안녕하세요! 오늘은 백준의 Platinum_III 난이도 문제인 "System Engineer"를 함께 풀어보는 시간을 갖겠습니다. 이 문제는 이분 매칭(Bipartite Matching) 알고리즘을 이용하여 해결할 수 있는 문제입니다.

1. 문제 소개

문제 번호: 3736
문제명: System Engineer
난이도 (티어): Platinum_III
사용 언어: C++
실행 시간: 708 ms
메모리: 3192 KB
문제 요약: 주어진 작업들이 가능한 서버 목록을 바탕으로, 최대 개수의 작업을 처리할 수 있도록 서버를 할당하는 문제입니다. 각 작업은 특정 서버들만 처리할 수 있으며, 한 서버는 한 번에 하나의 작업만 처리할 수 있습니다.

2. 접근 방법

이 문제는 최대 이분 매칭(Maximum Bipartite Matching) 문제로 볼 수 있습니다.

문제 이해:
작업(Job)과 서버(Server)라는 두 개의 집합이 있습니다. 각 작업은 자신이 처리 가능한 서버들의 집합에 대한 정보를 가지고 있습니다. 우리는 가능한 많은 작업을 서버에 할당해야 합니다. 이때, 각 작업은 하나의 서버에만 할당될 수 있고, 각 서버는 하나의 작업만 할당받을 수 있습니다.
알고리즘/자료구조 선택:
이러한 종류의 문제는 이분 그래프에서의 최대 매칭을 찾는 문제에 해당합니다. 따라서 헝가리안 알고리즘(Hungarian Algorithm) 또는 조르단-페르디낭 알고리즘(Jordan-Ferdinand Algorithm) 기반의 DFS를 이용한 이분 매칭 알고리즘을 사용합니다. 본 풀이에서는 DFS를 이용한 방법을 사용했습니다.
선택 이유:
DFS를 이용한 이분 매칭은 구현이 비교적 간단하면서도, 문제의 제약 조건(작업 및 서버의 개수가 최대 10,000개) 하에서 충분히 효율적인 성능을 보입니다. 또한, "증가 경로(Augmenting Path)"를 탐색하는 메커니즘을 통해 최대 매칭을 찾아냅니다.

3. 풀이 과정

이분 매칭 알고리즘의 핵심은 **증가 경로(Augmenting Path)**를 찾는 것입니다. 증가 경로란, 현재 매칭되지 않은 두 노드(이 문제에서는 작업과 서버)를 연결하며, 기존 매칭을 따라가는 엣지와 그 엣지의 방향을 번갈아 가며 구성되는 경로입니다. 증가 경로를 찾으면, 경로 상의 엣지들의 매칭 상태를 뒤집어(매칭된 것은 매칭 해제, 매칭 안 된 것은 매칭) 전체 매칭 수를 하나 늘릴 수 있습니다.

단계별 풀이 설명

데이터 구조:
- adj[MAX]: 각 작업 u가 처리 가능한 서버들의 목록을 저장하는 인접 리스트입니다.
- match[MAX]: 각 서버 v에 현재 어떤 작업 u가 할당되어 있는지 저장합니다. 초기값은 -1 (할당되지 않음)입니다.
- visited[MAX]: DFS 탐색 중 해당 서버 v를 이미 방문했는지 여부를 나타냅니다. 이는 한 번의 DFS 탐색 내에서 무한 루프를 방지하고, 효율적으로 증가 경로를 탐색하는 데 사용됩니다.
DFS 함수 (dfs(int u)):
- 이 함수는 작업 u를 매칭할 수 있는 서버를 찾는 역할을 합니다.
- 작업 u가 처리 가능한 서버 v들을 순회합니다.
- 만약 서버 v가 아직 visited 상태가 아니라면:
  - visited[v]를 true로 설정합니다.
  - 만약 서버 v가 비어있거나 (match[v] == -1)
  - 또는 서버 v에 할당된 기존 작업 match[v]가 다른 서버를 찾을 수 있다면 (dfs(match[v])가 true를 반환하면):
    - 서버 v를 작업 u에 할당합니다 (match[v] = u).
    - 매칭에 성공했으므로 true를 반환합니다.
- 모든 서버를 시도해도 매칭에 실패하면 false를 반환합니다.
메인 함수 (main()):
- 입력을 EOF까지 반복해서 받습니다. 각 테스트 케이스마다:
- 초기화:
  - adj 리스트를 비웁니다.
  - match 배열을 모두 -1로 초기화합니다.
- 입력 처리:
  - 각 작업 i에 대해, 해당 작업을 처리할 수 있는 서버 번호들을 읽어 adj[i]에 추가합니다. 입력 형식은 "작업번호: (서버 개수) 서버번호1 서버번호2 ..." 입니다.
- 이분 매칭 수행:
  - totalMatches 변수를 0으로 초기화합니다.
  - 모든 작업 i (0부터 n-1까지)에 대해:
    - visited 배열을 모두 0으로 초기화합니다. (각 작업의 DFS 탐색은 독립적이기 때문입니다.)
    - dfs(i)를 호출하여 작업 i를 매칭 시도합니다.
    - dfs(i)가 true를 반환하면, 매칭 수가 하나 늘어났으므로 totalMatches를 1 증가시킵니다.
- 결과 출력:
  - 최대로 매칭된 작업 수를 totalMatches에 출력합니다.

핵심 아이디어

증가 경로 탐색: DFS를 통해 현재 매칭되지 않은 노드로부터 시작하여, 기존 매칭에 얽매이지 않고 매칭 수를 늘릴 수 있는 경로를 재귀적으로 탐색합니다.
visited 배열의 활용: 각 DFS 호출 시 visited 배열을 초기화하여, 특정 서버가 현재 탐색 중인 작업에 대한 "양보 요청"을 이미 받았는지 추적합니다. 이는 무한 루프를 방지하고, 효율적인 탐색을 가능하게 합니다.

주의할 점

visited 배열 초기화: 매 작업(i in 0 to n-1)마다 visited 배열을 반드시 초기화해야 합니다. 그렇지 않으면, 이전 작업에서 사용했던 visited 상태가 다음 작업의 매칭 탐색에 영향을 미쳐 올바르지 않은 결과를 초래할 수 있습니다.
각 테스트 케이스 초기화: 각 테스트 케이스마다 adj 리스트와 match 배열을 초기화해야 합니다.

4. 코드 설명

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

// 최대 노드 수 설정 (n은 최대 10,000)
const int MAX = 20001;
vector<int> adj[MAX]; // 인접 리스트: 작업이 어떤 서버와 연결될 수 있는지 알려주는 작업 i의 서버 번호 목록
int match[MAX];    // 서버가 어떤 작업과 연결되어 있는지 저장
bool visited[MAX];    // 한 번의 탐색(DFS)에서 해당 서버 v를 이미 방문했는지 체크

// DFS 함수: 작업 u를 담당할 수 있는 서버들 고유번호들을 v : adj[u]로 각각 시도해보며 
// 작업 u를 감당가능한 서버 v를 찾아보자.
bool dfs(int u) {                     // 작업 u를 입력하면
    for (int v : adj[u]) {              // 작업 u가 처리될 수 있는 서버들 고유번호들을 순회하며 빈 서버가 있는지 보자.
        if (visited[v]) continue;
        visited[v] = true; 
        // visited[v] = true는 "이번 작업 u의 대타를 찾는 과정에서, 이미 서버 v한테 물어봤다는 뜻입니다. 
        
        // n번째 작업이 한 서버 v와 매칭이 됐다고 합시다.
        // n+1번째 작업 입장에서 n번째 작업이 매칭된 서버 v가 본인을 처리할 수 있는 유일한 서버라고 합시다.
        // 이러면 최대한 매칭 수를 늘리기 위해 n번째 작업이 양보를 해줘야 합니다.
        // 이때 n번째 작업 매칭 후 visited를 초기화하지 않았다면 n+1번째 작업 매칭 때에는 서버 v가 visited이므로
        // 양보 요청을 못하게 됩니다. 즉 최대 매칭 수를 구하지 못하게 됩니다.
        // 그러므로 visited는 매 작업 매칭 전에 이번 작업이 이전 작업들에게 양보요청을 보내려면 초기화되어야 합니다. 
        
        
        // visited은 매칭 기록이 아닙니다. 매칭 기록은 match[서버번호]로 파악합니다.
        // 1. 서버 v가 처리 중인 작업이 없으면 u를 담당해준다.             <= match[v] == -1
        // 2. 서버 v가 처리 중인 작업(match[v]) u*가 있으면             <= match[v] != -1
        // u*를 다른 서버가 담당하게 한다 <= dfs(match[v])
        // 만약 담당해줄 다른 서버를 끝내 못 찾으면, 
        // 서버 v가 처리 중인 작업 있었고 대타해줄 서버도 못 구했으니 
        // 작업 u는 서버를 배정받지 못하고 노는 작업이 된다.
        // return false;
        
        // 서버 v가 비어있었으면, v --- u로 매칭되고
        // 차있더라도 v가 담당했던 작업 u*(u 아님)을 대타해줄 서버 v*(v 아님)를 찾았다면,
        // v* --- u* <= v가 담당하던 u*를 처리해줄 대타 서버 v*를 구했고
        //  v --- u <= v가 u를 담당하게 할 수 있습니다.
        // 혼자가 된 서버 v를 작업 u가 담당하게 한다. <= match[v] = u;
        
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u; // 서버 v를 작업 u에게 배정
            return true;  // 매칭 성공!
        }
    }
    return false; // 끝내 매칭 실패
}

int main() {
    int n;
    // EOF(파일 끝)까지 반복해서 입력받음
    while (scanf("%d", &n) != EOF) {
        // 1. 초기화: 매 케이스마다 그래프와 매칭 기록을 비워야 함
        for (int i = 0; i < n; i++) // 모든 작업들에 대해 서버와 매칭한 그래프 지우기
            adj[i].clear(); // 작업 i가 어떤 서버와 매칭 가능한지를 알려주는 인접 리스트 초기화.
        
        fill(match, match + MAX, -1); // 서버 입장에서 작업과 매칭된 정보 리스트 -1로 초기화

        // 2. 입력 처리: "0: (3) 4 5 6" 형태를 파싱 
        //    형식은 작업번호: (해당 작업을 처리할 수 있는 서버 개수) 해당 작업을 처리할 수 있는 서버 번호들
        
        for (int i = 0; i < n; i++) { // 한 데이터 세트에 대해 작업은 총 n개이므로 n개의 작업에 대한 정보를 입력받는다.
            int u, count;              // 이번에 입력받는 작업 번호 u
            scanf("%d: (%d)", &u, &count); // 이번에 입력받은 작업을 처리할 수 있는 서버 수 count  
            for (int j = 0; j < count; j++) { // 이번에 입력받는 작업을 처리할 수 있는 서버들의 고유 번호 v
                int v;
                scanf("%d", &v);
                adj[u].push_back(v); // 작업 u에서 서버 v로의 간선 추가
            }
        }

        // 3. 이분 매칭 수행
        int totalMatches = 0;
        for (int i = 0; i < n; i++) { // i는 작업 번호
            // 매 작업마다 서버 v가 점유 상태인지 알게 해주는 visited 배열 초기화하고 다시 매칭 
            // => 매 작업마다 visited를 초기화해주는 이유
            //  $u$ 가  $v$ 에게 양보 요청  $\to$   $v$ 의 주인  $u^{'}$ 이 다른 서버  $v^{'}$ 에게 양보 요청...
            // 이 과정에서 다시  $v$ 에게 돌아오는 **순환(Cycle)**이 생기면 프로그램이 멈추지 않습니다.
            // 반대로 visited를 사용하고 continue 문 넣으면? 한번 양보요청으로 
            // v  x  1   7  ...  23   1  양보요청 흐름 : 0 -> 1 -> 8 -> 7 -> ... -> 23 -> 53 -> 1 (첫 양보요청으로 돌아옴)
            // u  0  8   2  ...  53   8  이런 식으로 u가 다음 u* (코드상에선 dfs(match[v]))에게 
            // 계속 양보요청을 보내다보면 작업 53이 서버 1에게 양보요청을 하면서 
            // 8번 작업이 또 7번 서버에게 양보요청... 하는 무한 사이클이 생겨버림. 
            // 그럼 이런 상황에서 continue가 있었다면 매번 양보요청(e.g. dfs(match[1]))을 하기 전에 
            // visited에 작업 i에 대해 매칭하는 과정에서 양보요청했던 모든 서버 번호가 
            // visited에 저장되어있으니 53번 작업이 또 1번 서버에 양보요청을 할 수가 없게됨. 
            // 왜냐면 0번 작업이 처음 양보요청 보낸 곳이 1번 서버여서 이미 visited에 1번이 true로 기록되었기 때문.
            // 53번 작업을 매칭할 서버 찾는 중에 if (visited[v]) continue;에 의해서 
            // visited 처리됐던 1번 서버는 스킵되어 양보요청을 보내는 조건절까지 진입하지 못하기 때문임. 
            // 만약 53번을 대신 맡아줄 서버가 없으면(adj[53]가 동난 경우) 끝내 실패하여 false를 반환하게 될 것임. 
            // 0이 1번 서버에 양보요청을 보내면서 여러 분기가 생겼을 거라 가정해보자. 
            // 중간 중간에 트리형식으로 계속 다른 서버의 매칭되어있던 작업들도 가지 치듯이 
            // 양보요청을 다른 서버들에게 보낼 건데 visited 덕분에 사이클 구조는 생기지 못하게 됨. 
            // 만약 사이클 즉 다시 첫 양보요청한 노드로 돌아오게 되면 visited에 의해 인접 리스트가 동나고
            // 실패로 결론난다. 
            // 이런 문제에서 모든 나뭇가지들은 그 끝이 실패 혹은 성공(match[v] == -1 빈 서버)으로 끝나면서
            // 그 결론을 맨 처음 dfs(i)가 반환하여 totalMatches++ 할지 말지 할 수 수 있게 되는 거임.

            fill(visited, visited + MAX, 0);
            
            if (dfs(i)) { // 매 작업에 대해 하나의 서버를 매칭 시도. 
                // dfs 함수 내에서 해당 작업을 처리 가능한 고유번호의 서버 v가 비었으면 바로 매칭 성공.
                // 안 비었으면, 서버 v가 담당 중인 작업 u*을 다른 서버 v*가 대타로 담당해줄 수 있는지 보고 
                // 가능하면 담당하던 작업 u*을 대타 서버 v*랑 매칭시킨다.
                // 그러면 서버 v에게 여유가 생겼으니 서버를 구하던 u 작업을 비워진 서버 v와 매칭하게 된다.
                
                // 재귀 dfs이기 때문에 연쇄적으로 작업들이 대타를 구하고 끝에서 대타가 구해지면 스택이 돌아오면서 매칭이 연달아 성공할 수도 있다.  
                // 재귀의 연쇄 반응: dfs(match[v])가 단순히 한 명의 대타를 찾는 게 아니라, 
                // "대타의 대타의 대타..." 즉 "dfs(match[v])의 dfs(match[v])의 dfs(match[v])의 dfs(match[v])" 
                // 까지 타고 들어가서 결국 마지막에 빈 서버(match[v] == -1)를 찾아내면, 
                // 그 성공 신호(true)가 돌아오며 줄줄이 매칭을 갱신한다.
                
                totalMatches++;
            }
        }

        // 4. 결과 출력
        printf("%d\n", totalMatches);
    }
    return 0;
}

주요 부분 설명

dfs(int u) 함수는 작업 u를 위한 증가 경로를 찾는 재귀 함수입니다.
match[v]는 서버 v가 현재 어떤 작업 u에 할당되었는지를 기록하며, -1이면 할당되지 않았음을 의미합니다.
visited[v]는 현재 DFS 탐색 중 서버 v를 방문했는지 여부를 나타내어, 사이클 발생을 방지하고 효율성을 높입니다.
main 함수에서는 각 작업 i에 대해 dfs(i)를 호출하며, 매칭 성공 시 totalMatches를 증가시킵니다. visited 배열은 각 작업 i마다 독립적인 탐색을 보장하기 위해 초기화됩니다.

코드 주석

코드 내에 각 부분의 역할과 동작 원리에 대한 자세한 주석이 포함되어 있습니다. 특히 visited 배열의 중요성과 dfs 함수의 재귀적 동작 방식에 대한 설명을 참고하시면 이해에 큰 도움이 될 것입니다.

5. 복잡도 분석

시간 복잡도:
이분 매칭에서 DFS를 사용하는 알고리즘의 시간 복잡도는 일반적으로 $O (V \times E)$ 입니다. 여기서 $V$ 는 정점의 수(작업 수 + 서버 수), $E$ 는 간선의 수(가능한 작업-서버 연결 수)입니다.
이 문제에서 최대 작업/서버 수는 $N$ (최대 10,000)이라고 가정하면, 모든 작업에 대해 DFS를 수행하며, 각 DFS는 최대 $E$ 개의 간선을 탐색할 수 있습니다. 따라서, 대략 $O (N \times E)$ 가 됩니다. 하지만 실제로는 더 개선된 $O (E V)$ 또는 $O (V^{3})$ 등의 복잡도를 가지는 알고리즘들도 존재합니다. 본 문제에서는 $N$ 이 크기 때문에 $O (N^{2})$ 가 될 수도 있고, $E$ 의 크기에 따라 달라질 수 있습니다. 문제의 특성상, 각 작업이 연결되는 서버 수가 많지 않다면 실제로는 더 빠르게 동작할 수 있습니다.
공간 복잡도:
adj 리스트, match 배열, visited 배열 등이 사용되므로, 공간 복잡도는 $O (V + E)$ 또는 $O (N + E)$ 가 됩니다. 여기서 $N$ 은 작업의 최대 개수이고, $E$ 는 가능한 연결의 총 개수입니다.

6. 배운 점

이 문제를 풀면서 다음과 같은 내용을 배울 수 있었습니다.

이분 매칭의 개념 및 DFS 활용: 이분 그래프에서의 최대 매칭을 DFS를 이용한 증가 경로 탐색으로 해결하는 방법을 깊이 이해할 수 있었습니다.
visited 배열의 역할: DFS 기반 매칭 알고리즘에서 visited 배열이 단순히 방문 여부를 체크하는 것을 넘어, 증가 경로 탐색 중 무한 루프 방지와 효율적인 탐색에 얼마나 중요한 역할을 하는지 알게 되었습니다.
매 테스트 케이스 초기화의 중요성: 여러 테스트 케이스를 처리하는 문제에서는 각 케이스별로 사용된 자료구조(인접 리스트, 매칭 정보, 방문 정보 등)를 완벽하게 초기화해야 함을 다시 한번 상기할 수 있었습니다.

이러한 이분 매칭 알고리즘은 작업 할당, 자원 배분, 스케줄링 등 다양한 실제 문제에 응용될 수 있습니다. 이 문제 풀이를 통해 얻은 지식을 바탕으로 다른 유사한 문제들도 자신감 있게 해결할 수 있을 것입니다.

감사합니다!
```