[Algorithm] cpp 백준 12963번: 달리기

도로 i의 용량이 3^i인 무향 그래프에서 0→N-1로 도달 가능한 최대 인원을 구한다. 3의 거듭제곱 가중치의 유일성으로 최소 s-t 컷이 단일해가 되며, 간선을 인덱스 내림차순으로 확인하며 DSU로 s와 t를 잇는 간선만 더해 합을 구해 1e9+7로 출력한다.

문제

링크: https://www.acmicpc.net/problem/12963
요약: 각 도로 i는 최대 3^i명이 통과 가능하다. 0번에서 N-1번으로 도달할 수 있는 사람 수의 최댓값을 1,000,000,007로 나눈 값을 구한다.
제한/스펙: 2 ≤ N ≤ 2000, 0 ≤ M ≤ 2000, 무향 그래프, 동일 간선 중복 없음

입력/출력

1
2
예시 출력
10

접근 개요

각 간선의 용량이 3^i로 서로 다른 자리값을 가지므로 어떤 s-t 컷의 총합은 기수 3 표현처럼 유일하다.
따라서 최소 s-t 컷은 “가중치가 큰 간선을 우선 고려”하는 그리디로 판별 가능하다.
간선을 인덱스 내림차순(i = M-1 → 0)으로 보며, 해당 간선을 추가했을 때 s와 t가 연결되면 그 간선은 컷에 포함(합에 3^i 더함), 아니면 컴포넌트를 합친다(DSU).

알고리즘

간선을 입력 순서(= 인덱스)대로 저장하고, i = M-1..0 순으로 처리한다.
현재 DSU에서 find(0)과 find(N-1)이 서로 다른 상태를 유지하며, 간선 (u,v)가 s-측과 t-측을 직접 잇는다면 컷에 포함하고 답에 3^i를 더한다.
그렇지 않다면 u와 v를 유니온한다.
모든 간선을 처리한 총합을 MOD=1,000,000,007로 출력한다.

올바름 근거(스케치): 3^i 가중치는 자리값이 커서 상위 인덱스를 이기는 어떤 조합도 존재하지 않으므로, 내림차순으로 “상위 간선이 컷에 들어갈지”를 그 순간의 s/t 분할로 확정해도 전역 최소 컷과 일치한다. 이는 이진(또는 기수) 유일 표현 기반의 그리디 정당화와 동일한 논리다.

복잡도

시간: O(M · α(N)) (DSU 상수 포함)
공간: O(N + M)

구현 (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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

struct DisjointSetUnion {
	vector<int> parent;
	vector<int> size;
	DisjointSetUnion(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
	int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
	bool unite(int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return false;
		if (size[a] < size[b]) swap(a, b);
		parent[b] = a;
		size[a] += size[b];
		return true;
	}
};

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

	int N, M;
	if (!(cin >> N >> M)) return 0;

	vector<pair<int,int>> edges(M);
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		edges[i] = {a, b};
	}

	vector<long long> pow3(max(1, M + 1), 1);
	for (int i = 1; i <= M; ++i) pow3[i] = (pow3[i - 1] * 3) % MOD;

	DisjointSetUnion dsu(N);
	long long answer = 0;

	for (int i = M - 1; i >= 0; --i) {
		int u = edges[i].first;
		int v = edges[i].second;
		int ru = dsu.find(u);
		int rv = dsu.find(v);
		int rs = dsu.find(0);
		int rt = dsu.find(N - 1);

		if (ru == rv) continue;

		bool connectsST = (ru == rs && rv == rt) || (ru == rt && rv == rs);
		if (connectsST) {
			answer += pow3[i];
			if (answer >= MOD) answer -= MOD;
		} else {
			dsu.unite(ru, rv);
		}
	}

	cout << (answer % MOD) << '\n';
	return 0;
}