문제
N명의 사람과 K가지 떡국이 있다. 각 사람은 특정 떡국의 재료를 갖고 있고, 특정 떡국을 먹고 싶어한다. 사람 간 재료 교환이 가능할 때, 떡국을 먹을 수 있는 최대 인원을 구하라.
입력
첫째 줄에 N, 이후 N x N 인접 행렬(교환 가능 여부), K, 각 사람의 보유 재료 목록과 희망 떡국 목록이 주어진다.
출력
떡국을 먹을 수 있는 최대 인원을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 011 101 110 2 1 0 1 1 1 0 1 1 1 0 1 1 | 3 |
풀이
K가지 떡국 각각에 대해 최대 유량(Edmonds-Karp) 알고리즘을 적용한다.
- 각 떡국 i에 대해 네트워크 플로우 그래프를 구성한다
- 소스(0)에서 재료를 가진 사람에게 INF 용량 간선 연결
- 사람 간 교환 가능 관계를 인접 행렬의 용량으로 설정
- 해당 떡국을 원하지 않는(먹을 수 있는) 사람에서 싱크(N+1)로 INF 용량 간선 연결
- BFS로 증가 경로를 찾아 유량을 보내는 과정을 반복한다
- K가지 떡국의 최대 유량 합이 정답이다
핵심 아이디어: 재료를 가진 사람 → 교환 네트워크 → 떡국을 먹을 수 있는 사람으로의 최대 유량이 곧 해당 떡국을 먹을 수 있는 최대 인원이다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day350BOJ1127떡국 { // g선생님
static int N, K, t, ans = 0, INF = (int) 1e9;
static int[][] c, s, e;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
t = N + 1;
c = new int[t + 1][t + 1];
for (int i = 1; i <= N; i++) {
String tmp = br.readLine();
for (int j = 0; j < N; j++)
c[i][j + 1] = tmp.charAt(j) - '0';
}
K = Integer.parseInt(br.readLine());
s = new int[K][N + 1];
e = new int[K][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
while (cnt-- > 0)
s[Integer.parseInt(st.nextToken())][i]++;
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
while (cnt-- > 0)
e[Integer.parseInt(st.nextToken())][i]++;
}
for (int i = 0; i < K; i++) {
for (int j = 1; j <= N; j++) {
c[0][j] = c[j][t] = 0;
if (s[i][j] == 1)
c[0][j] = INF;
if (e[i][j] == 0)
c[j][t] = INF;
}
int f[][] = new int[t + 1][t + 1];
while (true) {
int p[] = new int[t + 1];
for (int j = 1; j <= t; j++)
p[j]--;
Queue<Integer> q = new LinkedList<>();
q.add(0);
Loop: while (!q.isEmpty()) {
int cur = q.poll();
for (int next = 1; next <= t; next++) {
if (c[cur][next] > f[cur][next] && p[next] == -1) {
p[next] = cur;
if (next == t)
break Loop;
q.add(next);
}
}
}
if (p[t] == -1)
break;
for (int j = t; j > 0; j = p[j]) {
f[p[j]][j]++;
f[j][p[j]]--;
}
ans++;
}
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(K * V * E²) (V = N+2, E = N², Edmonds-Karp)
- 공간: O(N²)