import sys
input = sys.stdin.readline
mod = 1000003
def multiply(A,B):
result = [[0]*len(A) for i in range(len(A))]
for i in range(len(A)):
for j in range(len(A)):
for k in range(len(A)):
result[i][j] += A[i][k]*B[k][j]
result[i][j] %= mod
return result
def cal(A,n):
if n == 1:
return A
cal2 = cal(A,n//2)
if n%2 == 0:
return multiply(cal2,cal2)
else:
return multiply(multiply(cal2,cal2),A)
N,S,E,T = map(int,input().split())
matrix = []
for i in range(N):
matrix.append([*map(int,input().strip())])
newN = N
newi = {}
for i in range(N):
maxi = max(matrix[i])
if maxi>1:
newi[i] = newN
newN += maxi-1
newmatrix = [[0]*newN for i in range(newN)]
for i in range(N):
for j in range(N):
if matrix[i][j] == 1:
newmatrix[i][j] = 1
if matrix[i][j] > 1:
now = i
for next in range(newi[i],newi[i]+matrix[i][j]-1):
newmatrix[now][next] = 1
now = next
newmatrix[now][j] = 1
solve = cal(newmatrix,T)
print(solve[S-1][E-1])
전체적인 알고리즘은 본대산책2 [백준 12850번] 본대 산책2 (Python3) (tistory.com) 와 비슷한 문제이다.
인접행렬을 구한 뒤, 걸리는 시간만큼 인접행렬을 거듭제곱하여 경우의 수를 구하면 된다.
본대 산책2와의 차이점은 이동시간이 모두 똑같이 1이 아니라 1~5까지 달라진다는 점이다.
이를 어떻게 해결할까 생각하다가, 걸리는 시간만큼 노드를 쪼개주면 되겠다고 생각했다.
예를들어 1>>3까지 걸리는 시간이 2라면, 새로운 노드 4를 추가하여, 1>>4>>3으로 경로를 수정하는 것이다.
경로수정을 한 방법은 다음과 같다.
1. 각 행마다 최대 걸리는 시간을 측정하고, 1보다 크면 그 차이만큼 N의 크기를 늘린다.
2. 1 에서 각 행마다 새로운 노드의 시작지점도 지정해주어야한다. (예를들어 만약 처음 N이 3이고 N의 크기를 2만큼 늘린다면 4~5까지가 현재 행이 소유(?) 한 노드이다)
3. 새로운 N에 대하여 newN*newN의 새로운 행렬을 만들고, 시간이 1보다 큰 지점에 한하여 경로를 수정해준다.
4. 분할제곱을 통한 거듭제곱으로 결과를 출력한다.
처음에는 모든 항마다 시간이 1보다 클때마다 새로운 행을 추가해야한다고 생각했다. 그러나 그렇게 제출하니 시간초과가 났고, (만약 모든 항이 5라면 N이 5*100이 될테니...) 같은 행에서는 새로운 행을 추가할 필요 없이 같이 경로를 수정할 수 있다는 것을 알게되었다.
오늘의 교훈) 이전에 푼 문제를 응용하면 어려운 문제도 쉽게 해결할 수 있다.