백준 1533: 길의 개수

https://www.acmicpc.net/problem/1533

이 문제를 풀기 위해서는 

https://www.acmicpc.net/problem/12850

이 문제 부터 해결해야한다.

위의 문제의 해결법은

https://sumserv.tistory.com/92

백준 12850: 본대 산책2

이전에 다뤘으므로 생략한다.

 

큰 차이점은 가중치가 생겼다는 점이다. 이전 문제에서는 있다 없다를 길로 표현했는데, 가중치가 생겨서, 단순하게 행렬의 곱셈으로 풀기엔 힘들어보인다.

 

여기서 눈에 가는 것은 가중치 부분이다  가중치는 A[i][j] ≤ 5로 굉장히 짧다. 여기에 N은 10보다 작은 굉장히 작은 수이다.

나는 이 부분에서 하나의 아이디어를 떠올렸다. 가중치를 노드로 바꾸는 것이다.

 

더 설명을 하자면, 노드 하나를 다섯개의 노드로 바꾼다.

만약 1번 노드가 2번 노드를 3의 가중치로 연결한다면, 1번 노드는 5~9번 노드, 2번 노드는 10~14번 노드로 변환하고

변환된 노드들은 선형적으로 연결한다.(5-6, 6-7, 7-8, 8-9) 여기에 7번 노드와 10번 노드를 연결한다. 각 5번, 10번이 원래의 노드의 대표라 한다면, 5번 노드가 10번 노드로 가는 가중치는 3이 되기의 본래의 그래프와 같게 된다. 즉, 이런 방식으로 그래프를 변환하고, 12850을 풀었던 방식을 적용하면 문제는 쉽게 해결된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
using mat = vector<vector<ll>>;
int N, S, E, T;
mat adj(52, vector<ll>(52));
char ch;
const ll MOD = 1000003;

mat multiply(mat& a, mat& b)
{
	mat ret(52, vector<ll>(52, 0L));
	for (int i = 0; i < 52; i++)
		for (int j = 0; j < 52; j++)
		{
			for (int k = 0; k < 52; k++)
			{
				ret[i][j] += a[i][k] * b[k][j];
				ret[i][j] %= MOD;
			}
		}
	return ret;
}
mat mulRepeat(int n, mat& m)
{
	if (n == 1) return m;
	if (n % 2 > 0)
	{
		mat tmp = mulRepeat(n - 1, m);
		return multiply(m, tmp);
	}
	mat a = mulRepeat(n / 2, m);
	return multiply(a, a);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> S >> E >> T;
	--S; --E;
	for (int n = 0; n < N; n++)
	{
		for (int i = 1; i < 5; i++)
			adj[n * 5 + i][n * 5 + i - 1] = 1;
	}
	for(int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
		{
			cin >> ch;
			if (ch == '0') continue;
			int n = (ch - '0');
			adj[y * 5][x * 5 + n - 1] = 1;
		}
	mat ans = mulRepeat(T, adj);
	cout << ans[S * 5][E * 5] << '\n';
}

역시 문제는 많이 푸는 것이 중요하다는 것을 새삼 느끼게 되었다. 이러한 방식으로 해결하는 문제를 이전에 풀어서, 이 해결방식을 쉽게 떠올렸다. 다만 생각보다 구현에 애먹은 것이 걸린다. 다음부터는 좀 더 생각을 정리하는 습관을 가지자.