https://www.acmicpc.net/problem/2188
문제 이해
농부 존의 축사에 N마리의 소를 M개의 축사에 배정하는 문제입니다. 각 소는 자신이 원하는 특정 축사들에만 들어가려 하고, 한 축사에는 최대 1마리의 소만 들어갈 수 있습니다.
목표: 최대한 많은 소를 축사에 배정하기
핵심 아이디어: 이분 매칭
이 문제는 **이분 매칭(Bipartite Matching)**의 대표적인 예시입니다. 두 그룹(소 vs 축사) 사이의 최적 매칭을 찾는 문제죠.
왜 단순한 탐욕법으로는 안 될까?
소1: 축사 2, 5 선택 가능
소5: 축사 2만 선택 가능
만약 소1이 축사2를 먼저 차지하면, 소5는 들어갈 곳이 없어집니다. 하지만 소1이 축사5로 "양보"하면, 소5가 축사2에 들어갈 수 있어 전체 매칭 수가 늘어납니다.
해결 방법: DFS + 양보 알고리즘
핵심은 **"이미 배정된 소라도, 다른 축사로 양보할 수 있다면 양보시키기"**입니다.
알고리즘 구조
- 각 소에 대해 축사 배정 시도
- 원하는 축사가 이미 점유되었다면, 그 축사의 주인 소를 다른 곳으로 이동 시도
- 성공하면 현재 소를 그 축사에 배정
코드 구현
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_N 201
#define MAX_M 201
int N, M;
bool graph[MAX_N][MAX_M]; // graph[cow][barn]: cow가 barn을 원하면 true
int match[MAX_M]; // match[barn]: 배정된 cow (없으면 -1)
bool visited[MAX_M]; // DFS 한 번마다 축사 방문 체크
bool dfs(int cow) {
for (int barn = 1; barn <= M; barn++) {
if (!graph[cow][barn]) continue; // 이 소가 원하지 않는 축사
if (visited[barn]) continue; // 이미 확인한 축사
visited[barn] = true;
// 축사가 비어있거나, 기존 소를 다른 축사로 보낼 수 있으면 배정
if (match[barn] == -1 || dfs(match[barn])) {
match[barn] = cow;
return true;
}
}
return false;
}
int main(void) {
scanf("%d %d", &N, &M);
memset(graph, 0, sizeof(graph));
for (int i = 1; i <= M; i++) match[i] = -1;
// 입력 처리
for (int c = 1; c <= N; c++) {
int s; scanf("%d", &s);
for (int k = 0; k < s; k++) {
int barn; scanf("%d", &barn);
graph[c][barn] = true;
}
}
int result = 0;
// 각 소마다 매칭 시도
for (int c = 1; c <= N; c++) {
memset(visited, 0, sizeof(visited)); // 매번 초기화!
if (dfs(c)) result++;
}
printf("%d\n", result);
return 0;
}
핵심 포인트 분석
1. 양보 메커니즘
if (match[barn] == -1 || dfs(match[barn])) {
match[barn] = cow;
return true;
}
이 한 줄이 바로 "양보" 로직입니다:
- match[barn] == -1: 축사가 비어있으면 바로 배정
- dfs(match[barn]): 기존 주인을 다른 곳으로 보낼 수 있으면 양보
2. visited 배열의 역할
visited 배열은 각 소마다 새로 초기화됩니다. 이는 무한 루프를 방지하고, 각 매칭 시도가 독립적으로 이루어지도록 합니다.
3. 실행 과정 예시
소2가 축사2를 원함 (이미 소1이 점유)
→ dfs(1) 호출: "소1을 다른 곳으로 보낼 수 있나?"
→ 소1이 축사5로 이동 가능 ✅
→ 소1을 축사5로 이동, 소2를 축사2에 배정 ✅
최적화 버전: 인접리스트
더 효율적인 구현을 위해 인접리스트 방식을 사용할 수 있습니다:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_N 201
#define MAX_M 201
int N, M;
int cowWants[MAX_N][MAX_M]; // cowWants[c][i]: c가 원하는 i번째 축사
int wantCnt[MAX_N]; // 각 소가 원하는 축사 개수
int matchBarn[MAX_M]; // matchBarn[barn]: 배정된 cow
bool visited[MAX_M];
bool dfs(int cow) {
for (int i = 0; i < wantCnt[cow]; i++) {
int barn = cowWants[cow][i];
if (visited[barn]) continue;
visited[barn] = true;
if (matchBarn[barn] == -1 || dfs(matchBarn[barn])) {
matchBarn[barn] = cow;
return true;
}
}
return false;
}
int main(void) {
scanf("%d %d", &N, &M);
memset(wantCnt, 0, sizeof(wantCnt));
for (int b = 1; b <= M; b++) matchBarn[b] = -1;
for (int c = 1; c <= N; c++) {
int s; scanf("%d", &s);
wantCnt[c] = s;
for (int i = 0; i < s; i++) {
int b; scanf("%d", &b);
cowWants[c][i] = b;
}
}
int result = 0;
for (int c = 1; c <= N; c++) {
memset(visited, 0, sizeof(visited));
if (dfs(c)) result++;
}
printf("%d\n", result);
return 0;
}
두 방식 비교
🔹 인접행렬 방식 (기본 코드)
- ✅ 구현 단순, 직관적
- ❌ 항상 1~M 전체 확인 필요
- ❌ 메모리 = O(N×M)
🔹 인접리스트 방식 (최적화 코드)
- ✅ 소가 원하는 축사만 탐색
- ✅ 메모리 효율적 = O(E), E는 총 희망 연결 수
- ❌ 구현이 약간 더 복잡
언제 어떤 방식을 사용할까?
- N, M ≤ 200 (백준 2188 같은 문제): 인접행렬이 구현 간편
- N, M 수천 이상 + 희소 그래프: 인접리스트가 성능상 유리
시간복잡도
- 최악의 경우: O(N × M × E)
- 실제로는: 훨씬 빠르게 동작
- N, M ≤ 200 수준에서는 충분히 빠름
핵심 요약
- 이분 매칭: 두 그룹 간 최적 매칭 찾기
- 양보 알고리즘: 이미 배정된 소도 다른 곳으로 이동 시도
- DFS: 재귀적으로 양보 가능성 탐색
- visited 초기화: 각 소마다 독립적인 매칭 시도
이분 매칭은 네트워크 플로우의 특수한 경우로 많은 실전 문제에서 활용되는 중요한 알고리즘입니다. 이 문제를 이해하면 네트워크 플로우 문제로 확장할 수 있습니다.