이분 매칭 알고리즘 : 백준 3736번 문제 탐구

백준 3736번 문제, 'System Engineer'를 풀면서 네트워크 플로우의 기본 중 기본인 이분 매칭(Bipartite Matching) 알고리즘을 깊이 있게 탐구했습니다. Gemini와의 대화를 통해 처음에는 막막했던 알고리즘의 원리를 이해하고, 직접 코드를 작성하고 분석하며 런타임 에러까지 해결하는 과정을 거쳤습니다.

오늘 공부한 주제

• 학습 주제: 백준 3736번 'System Engineer' 문제 풀이를 통한 이분 매칭 알고리즘 학습
• 학습 날짜: 2026년 1월 28일

어떤 궁금증에서 시작했나?

문제를 처음 마주했을 때, '서버'와 '작업' 간의 관계에서 최대 몇 개의 '일'을 처리할 수 있는지 묻는 것이 이분 매칭과 어떻게 연결되는지 감이 잡히지 않았습니다. 특히 '서버가 작업을 할 수 있다'는 조건이 '하나의 서버는 하나의 작업만, 하나의 작업은 하나의 서버만'이라는 제약 조건 하에 어떻게 최대 매칭을 이루는지 궁금했습니다.

주요 질문:

• 주어진 서버와 작업 연결 정보에서 어떻게 최대 매칭 수를 효율적으로 구할 수 있을까?
• 이분 매칭 알고리즘의 핵심은 무엇이며, 왜 DFS를 사용하는가?
• visited 배열의 역할과 match 배열의 의미는 무엇인가?
• 입력 순서에 따라 결과가 달라지는 것은 아닌가?

핵심 학습 내용

이분 매칭의 핵심 아이디어는 **"양보의 연쇄 고리"**를 찾는 데 있다는 것을 알게 되었습니다. 이는 **증가 경로(Augmenting Path)**를 찾는 과정과 동일하며, DFS를 통해 이를 효과적으로 구현할 수 있습니다.

1. 이분 그래프와 최대 매칭

• 이분 그래프: 정점을 두 그룹(서버 $U$, 작업 $V$)으로 나누고, 간선은 항상 다른 그룹의 정점만을 연결하는 그래프입니다. 이 문제에서는 서버와 작업 사이의 연결이 이에 해당합니다.
• 최대 매칭: 그래프에서 서로 끝점을 공유하지 않는 간선들의 집합 중, 간선의 수가 최대인 것을 찾는 것입니다. 즉, 최대한 많은 서버-작업 쌍을 만드는 것입니다.

2. DFS를 이용한 이분 매칭 (증가 경로 탐색)

이분 매칭 알고리즘의 핵심은 DFS를 사용하여 "증가 경로"를 찾는 것입니다. 증가 경로는 현재 매칭되지 않은 정점에서 시작하여, 매칭되지 않은 간선과 매칭된 간선을 번갈아 가며 탐색하다가 마지막에 매칭되지 않은 정점으로 끝나는 경로를 말합니다.

• dfs(int u) 함수: 작업 u에 대해 가능한 서버 v를 탐색합니다.
  • adj[u]에는 작업 u가 처리 가능한 서버들의 목록이 저장되어 있습니다.
  • visited[v] 배열은 현재 진행 중인 dfs 호출 내에서 서버 v가 이미 탐색 대상에 올랐는지를 기록하여 무한 루프를 방지합니다. 이 배열은 메인 함수에서 매 작업에 대해 처리해줄 서버를 찾기위한 dfs(i) 호출 전에 매번 초기화되어야 합니다. (중요!)
  • match[v]는 서버 v가 현재 어떤 작업과 매칭되어 있는지를 저장합니다. -1이면 매칭되지 않은 상태입니다.
  • if (match[v] == -1 || dfs(match[v])): 이 부분이 핵심입니다.
    • match[v] == -1: 서버 v가 비어있으면, 작업 u를 바로 매칭합니다.
    • dfs(match[v]): 서버 v에 이미 작업(match[v])이 있다면, 그 작업에게 **"혹시 다른 서버로 옮겨갈 수 있니?"**라고 묻는 재귀 호출입니다. 만약 옮길 수 있다면, dfs(match[v])는 true를 반환하고, 현재 서버 v는 비게 됩니다.
  • 매칭에 성공하면 (true 반환), match[v] = u로 업데이트하고 true를 반환합니다.
• main 함수의 루프: 모든 작업(i from 0 to n-1)에 대해 dfs(i)를 호출하여 매칭을 시도합니다. dfs(i)가 true를 반환하면 totalMatches를 증가시킵니다.

3. 런타임 에러 해결과 배열 크기

처음 코드를 작성했을 때 런타임 에러가 발생했는데, 이는 배열 크기 문제 때문이었습니다. 문제 설명에서 서버 번호가 $n$부터 $2n-1$까지 나올 수 있는데, n이 10,000일 경우 서버 번호는 최대 19,999까지 나올 수 있습니다. 따라서 match와 visited 배열은 이 번호를 담을 수 있도록 충분히 커야 했습니다.

• 초기 MAX = 10001: 작업 번호(09999)는 커버했지만, 서버 번호(1000019999)를 커버하지 못했습니다.
• 수정 후 MAX = 20005: 서버 번호까지 안전하게 커버할 수 있도록 배열 크기를 늘렸습니다.
• 최적화: adj 배열은 작업 번호(0n-1)만 인덱스로 사용하므로 MAX_J = 10001로, match와 visited 배열은 서버 번호(n2n-1)를 사용하므로 MAX_S = 20001로 분리하여 메모리 효율성을 높였습니다.

새롭게 알게 된 것

• 이분 매칭의 핵심은 "양보": 단순히 비어있는 자리를 찾는 것이 아니라, 기존 매칭을 희생시켜서라도 전체 매칭 수를 늘리는 과정이 핵심입니다.
• DFS와 재귀의 역할: DFS의 재귀적 특성이 "연쇄적인 양보 요청"을 처리하고, 성공 시 결과를 위로 전달하는 데 최적임을 알게 되었습니다.
• visited 배열의 진정한 의미: visited는 단순히 방문 여부가 아니라, **"현재 작업의 대타 찾기 과정에 참여 중인 서버"**를 기록하여 무한 루프를 방지하는 역할을 한다는 것을 명확히 이해했습니다.
• 입력 순서와 최적성: 이분 매칭 알고리즘은 베르주의 정리에 의해 입력 순서와 관계없이 항상 그래프의 이론적 최대 매칭 수를 찾아낸다는 사실을 알게 되었습니다.
• 배열 인덱싱의 중요성: 문제에서 주어진 번호 체계를 정확히 파악하고, 이에 맞게 배열 크기를 설정하는 것이 런타임 에러를 방지하는 데 얼마나 중요한지 깨달았습니다.

실전 적용 및 실습 계획

• 개념 이해: 이분 매칭 알고리즘을 사용하여 팀 프로젝트에서 리소스 할당 문제 등을 모델링하고 해결하는 데 적용할 수 있을 것 같습니다. 예를 들어, 여러 개발자가 여러 작업 중 어떤 것을 할 수 있는지 주어졌을 때, 최대한 많은 작업을 효율적으로 분배하는 데 활용될 수 있습니다.
• 실습 계획:
  1. 백준의 다른 이분 매칭 문제들을 풀어보며 숙달하기 (예: 2188번 축사 배정, 11375번 열혈강호).
  2. 이분 매칭을 활용한 실제 시나리오를 가정하여 간단한 모델을 만들어보고 코드로 구현해보기.

🔍 추가 학습 계획

• 네트워크 플로우 심화: 이분 매칭을 바탕으로 최대 유량(Max Flow) 알고리즘(에드몬드-카프, 디닉)으로 넘어가 기본적인 네트워크 플로우 문제를 해결하는 방법을 학습하고 싶습니다.
• 시간 복잡도 최적화: $O(VE)$ 방식 외에 더 빠른 알고리즘(예: Hopcroft-Karp)의 원리를 파악해보고 싶습니다.

참고 자료

• Gemini와의 대화 내용 전체 (AI Chat Export)
• 백준 3736번 문제: https://www.acmicpc.net/problem/3736
• (Gemini가 추천했던) 이분 매칭 관련 알고리즘 설명 문서 및 그래프 이론 자료 (추후 탐색 예정)

이번 학습을 통해 이분 매칭이라는 강력한 알고리즘 도구를 얻게 되어 매우 기쁩니다. 복잡한 개념도 차근차근 파고들면 이해할 수 있다는 것을 다시 한번 느꼈습니다!
```