백준1533 길의 개수

작성일 | In

문제 링크

  • http://icpc.me/1533

사용 알고리즘

  • 인접행렬 거듭제곱

시간복잡도

  • O(N3lgT)

풀이

일단 인접행렬 거듭제곱(링크)로 풀릴 것 같이 생겼으니, 길이가 5 이하인 점에 초점을 두고 풀이를 구체화 시켜봅시다.

위 링크에 연결된 게시글에서는 가중치가 없는 그래프의 경우를 다뤘습니다. 가중치가 있는 경우에는 어떻게 해야할까요?
만약 두 정점 u, v의 거리가 3이라면, 두 정점 사이에 정점 2개를 추가로 넣어서 가중치가 1인 간선만을 이용해 그래프를 다시 만들 수 있습니다.

이제 구현 방법을 생각해봅시다.
모든 간선에 대해 더미 노드를 넣는다? 정점이 너무 많아지게 됩니다. 네트워크 플로우 문제에서 많이 사용했던 정점 분할 테크닉을 이용합시다.
정점 v를 {v, v1, v2, v3, v4}로 분할을 하고, 간선 (v4, v3), (v3, v2), (v2, v1), (v1, v)를 만들어줍시다.
만약 간선 (u, v)의 거리 dist가 1이라면 그대로 추가를 하고, dist가 1보다 크다면 (u, v(dist-1))을 추가해주면 됩니다.

행렬의 사이즈는 5N이 되고, T번 거듭제곱을 하기 때문에 O(N3logT)라는 효율적인 시간 복잡도로 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const ll mod = 1000003;

struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size = n;
		arr = vector< vector<ll> >(n, vector<ll>(n));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, s, e, t; cin >> n >> s >> e >> t;
	s--; e--;
	Matrix mat(n * 5);
	for(int i=0; i<n; i++){
		for(int j=1; j<5; j++){
			mat.arr[i*5+j][i*5+j-1] = 1;
		}
	}

	for(int i=0; i<n; i++){
		string str; cin >> str;
		for(int j=0; j<n; j++){
			int t = str[j] - '0';
			if(t == 1) mat.arr[i*5][j*5] = 1;
			else if(t > 1) mat.arr[i*5][j*5+t-1] = 1;
		}
	}

	Matrix ans = powmat(mat, t);
	cout << ans.arr[s*5][e*5];
}