[Python] 백준 1533 - 길의 개수

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

풀이

인접 행렬의 특징으로는,

A[i][j]가 정점 i에서 정점 j로 갈 수 있는 길의 개수라고 하면

A를 t번 거듭제곱한 행렬의 [x][y]는, 길을 t개 거쳐서 정점 x에서 정점 y까지 가는 경로의 개수이다.

여기서 알 수 있다

 

다만 이 문제에서는 길에 가중치가 있다. 단순히 주어진 행렬을 T번 곱한다고 해서 답이 나오지 않는다.

 

12850처럼 문제를 해결해주기 위해서, 인접행렬의 모든 원소를 1로 만들어주는 전략을 세우기 위해

그래프의 형태를 조금 바꿔주자!

 

길을 가는데 걸리는 시간이 1, 2, 3, 4, 5중 하나이므로 우리는 다음과 같은 전략을 세울 수 있다.

 

예를 들어 정점 2에서 1로 가는데 3분이 걸린다고 하자.

정점 1을 이제 1, 1-1, 1-2, 1-3, 1-4의 5개의 정점으로 쪼개자.

이 쪼개진 정점들은 유수풀마냥, 1-4 → 1-3 → 1-2 → 1-1 → 1 순으로 자동으로 이동하게끔 연결되어있다.

 

그렇다면, 정점 2에서 정점 1-2를 이어주면 자연스럽게 3분을 이동하는 것과 같은 효과를 낼 수 있다.

 

이렇게 만들어진 5N * 5N 인접행렬을 T제곱해주면 정답을 얻을 수 있다.

 

N, S, E, T = map(int, input().split())
MOD = 1_000_003
graph = [[0]*(5*N) for _ in range(5*N)]

for i in range(N):
    for j in range(4):
        graph[1+5*i+j][5*i+j] = 1


for i in range(N):
    tmp = list(map(int, list(input())))
    for j in range(N):
        if tmp[j]:
            graph[5*i][5*j + tmp[j] - 1] = 1


def mult(arr1, arr2):
    answer = [[0]*len(arr2[0]) for _ in range(len(arr1))]
    for i in range(len(arr1)):
        for j in range(len(arr2[0])):
            for k in range(len(arr1[0])):
                answer[i][j] += arr1[i][k] * arr2[k][j]
                answer[i][j] %= MOD
    return answer


def mpow(A, n):
    if n == 1:
        return A
    if n % 2 == 0:
        temp = mpow(A, n//2)
        return mult(temp, temp)
    else:
        temp = mpow(A, n-1)
        return mult(temp, A)

ans = mpow(graph, T)
print(ans[5*(S-1)][5*(E-1)])