[Algorithm] cpp-python 백준 13161번: 분단의 슬픔

문제

링크: BOJ 13161 분단의 슬픔
요약: 사람을 두 진영 A/B로 나눌 때, 서로 다른 진영에 속하면 발생하는 슬픔 비용 w[i,j]의 합을 최소화하라. 일부 사람은 반드시 A 또는 B에 속해야 한다.

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
<입력>
N
g1 g2 ... gN   (gi ∈ {0,1,2}; 1=A 강제, 2=B 강제, 0=자유)
w[1,1] ... w[1,N]
  ...         ...
w[N,1] ... w[N,N]   (대칭, 대각 0)

<출력>
최소 슬픔 합
A 진영 사람 번호들 (공백 구분, 없으면 빈 줄)
B 진영 사람 번호들 (공백 구분, 없으면 빈 줄)

접근 개요

핵심 모델링: 무향 가중 그래프의 두 집합 분할 비용 최소화는 s-t 최소 컷으로 풀 수 있다.
- w[i,j]는 간선 i↔j 용량 w[i,j]로 표현(양방향 간선 각 w).
- A 강제는 S→i에 INF 용량, B 강제는 i→T에 INF 용량으로 고정.
- 최소 컷 값 = 서로 다른 진영 간선들의 가중치 합.
알고리즘: Dinic(레벨 그래프 + 블로킹 플로우)로 최대 유량(=최소 컷) 계산. 잔여 그래프에서 S로부터 도달 가능한 정점을 A로, 나머지를 B로 복원.

flowchart TD
  A[입력 파싱] --> B[강제 조건: S→i (A), i→T (B) INF 간선 추가]
  B --> C[모든 i D[Dinic으로 최대유량 계산]
  D --> E[잔여 그래프에서 S-도달 집합 = A]
  E --> F[보완 집합 = B, 최소 컷 값 출력]

알고리즘 설계

정점: 1..N, 소스 S, 싱크 T.
간선 구성:
- 강제 A: S→i에 INF 용량.
- 강제 B: i→T에 INF 용량.
- 슬픔 비용: 모든 i<j에 i→j, j→i 각각 용량 w[i,j].
올바름 근거:
- 컷이 S-집합 | T-집합으로 나눌 때, 임의의 i∈S-집합, j∈T-집합에 대해 i→j가 컷을 가로지르며 용량 w[i,j]가 정확히 한 번만 더해진다(반대방향 간선은 컷에 포함되지 않음). 따라서 컷 값은 서로 다른 진영 간 간선 가중치 합과 일치한다.
- INF 간선은 해당 정점이 반대편으로 넘어가면 컷 값이 INF가 되어 최적해에서 이를 강제로 같은 편에 고정한다.

복잡도

시간: Dinic 최악 O(V^2 E), 실전에서는 O(E√V) 근사 성능. 여기서 V≈N+2≤502, E≈2·N(N-1)/2 + N ≤ 2.5e5 규모로 C++에서 충분히 통과.
공간: O(E).

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Edge {
    int to;
    int rev;
    int64 cap;
};

struct Dinic {
    int n, s, t;
    vector<vector<Edge>> g;
    vector<int> level, work;

    Dinic(int n, int s, int t) : n(n), s(s), t(t), g(n), level(n), work(n) {}

    void addEdge(int u, int v, int64 c) {
        Edge a{v, (int)g[v].size(), c};
        Edge b{u, (int)g[u].size(), 0};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    bool bfs() {
        fill(level.begin(), level.end(), -1);
        queue<int> q; level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (const auto& e : g[u]) if (e.cap > 0 && level[e.to] == -1) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
            }
        }
        return level[t] != -1;
    }

    int64 dfs(int u, int64 f) {
        if (u == t) return f;
        for (int& i = work[u]; i < (int)g[u].size(); ++i) {
            auto& e = g[u][i];
            if (e.cap <= 0 || level[e.to] != level[u] + 1) continue;
            int64 ret = dfs(e.to, min(f, e.cap));
            if (ret > 0) {
                e.cap -= ret;
                g[e.to][e.rev].cap += ret;
                return ret;
            }
        }
        return 0;
    }

    long long maxflow() {
        long long flow = 0;
        while (bfs()) {
            fill(work.begin(), work.end(), 0);
            while (true) {
                long long pushed = dfs(s, (long long)4e18);
                if (pushed == 0) break;
                flow += pushed;
            }
        }
        return flow;
    }

    vector<char> reachableFromSource() const {
        vector<char> vis(n, false);
        queue<int> q; q.push(s); vis[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (const auto& e : g[u]) if (e.cap > 0 && !vis[e.to]) {
                vis[e.to] = true; q.push(e.to);
            }
        }
        return vis;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; if (!(cin >> N)) return 0;
    const int S = 0, T = N + 1;
    Dinic din(N + 2, S, T);

    vector<int> force(N + 1);
    for (int i = 1; i <= N; ++i) cin >> force[i];

    // 읽으면서 i<j만 처리, 무향 간선을 양방향으로 추가
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            int w; cin >> w;
            if (j > i && w > 0) {
                din.addEdge(i, j, w);
                din.addEdge(j, i, w);
            }
        }
    }

    const long long INF = (long long)4e18;
    for (int i = 1; i <= N; ++i) {
        if (force[i] == 1) din.addEdge(S, i, INF);
        else if (force[i] == 2) din.addEdge(i, T, INF);
    }

    long long ans = din.maxflow();
    cout << ans << '\n';

    auto vis = din.reachableFromSource();
    bool first = true;
    for (int i = 1; i <= N; ++i) if (vis[i]) {
        if (!first) cout << ' ';
        cout << i; first = false;
    }
    cout << '\n';
    first = true;
    for (int i = 1; i <= N; ++i) if (!vis[i]) {
        if (!first) cout << ' ';
        cout << i; first = false;
    }
    cout << '\n';
    return 0;
}

구현 (Python)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
from collections import deque

def dinic_maxflow(n, s, t, graph):
    level = [-1] * n
    work = [0] * n

    def bfs():
        for i in range(n):
            level[i] = -1
        q = deque([s])
        level[s] = 0
        while q:
            u = q.popleft()
            for v, cap, rev in graph[u]:
                if cap > 0 and level[v] == -1:
                    level[v] = level[u] + 1
                    q.append(v)
        return level[t] != -1

    def dfs(u, f):
        if u == t:
            return f
        i = work[u]
        while i < len(graph[u]):
            v, cap, rev = graph[u][i]
            if cap > 0 and level[v] == level[u] + 1:
                pushed = dfs(v, f if f < cap else cap)
                if pushed:
                    graph[u][i][1] -= pushed
                    graph[v][rev][1] += pushed
                    return pushed
            i += 1
            work[u] = i
        return 0

    flow = 0
    INF = 10 ** 30
    while bfs():
        for i in range(n):
            work[i] = 0
        while True:
            pushed = dfs(s, INF)
            if not pushed:
                break
            flow += pushed
    return flow

def add_edge(graph, u, v, c):
    graph[u].append([v, c, len(graph[v])])
    graph[v].append([u, 0, len(graph[u]) - 1])

def main():
    input = sys.stdin.readline
    N_line = input().strip()
    if not N_line:
        return
    N = int(N_line)
    S, T = 0, N + 1
    n = N + 2
    graph = [[] for _ in range(n)]

    force = [0] * (N + 1)
    vals = list(map(int, input().split()))
    for i in range(1, N + 1):
        force[i] = vals[i - 1]

    W = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            w = W[i][j]
            if w:
                add_edge(graph, i + 1, j + 1, w)
                add_edge(graph, j + 1, i + 1, w)

    INF = 10 ** 30
    for i in range(1, N + 1):
        if force[i] == 1:
            add_edge(graph, S, i, INF)
        elif force[i] == 2:
            add_edge(graph, i, T, INF)

    min_cut = dinic_maxflow(n, S, T, graph)
    print(min_cut)

    # BFS on residual to get partition
    vis = [False] * n
    dq = deque([S])
    vis[S] = True
    while dq:
        u = dq.popleft()
        for v, cap, _ in graph[u]:
            if cap > 0 and not vis[v]:
                vis[v] = True
                dq.append(v)

    A = [str(i) for i in range(1, N + 1) if vis[i]]
    B = [str(i) for i in range(1, N + 1) if not vis[i]]
    print(" ".join(A))
    print(" ".join(B))

if __name__ == "__main__":
    main()