dy,dx = [1,-1,0,0],[0,0,1,-1]
mod = 10**9+7
def multiply(A,B):
result = [[0]*L for i in range(L)]
for y in range(L):
for x in range(L):
for i in range(L):
result[y][x] += A[y][i]*B[i][x]
result[y][x] %= mod
return result
def cal(A,N):
if N==1:
return A
C1 = cal(A,N//2); C2 = multiply(C1,C1)
return multiply(C2,A) if N%2 else C2
def solution(grid, D, k):
global N,M,L
N,M = len(grid),len(grid[0]); L = N*M
DP = [[[int(i==j) for i in range(L)] for j in range(L)]]+[[[0]*L for i in range(L)] for i in range(len(D))]
for d in range(len(D)):
for y in range(N):
for x in range(M):
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if 0<=y1<N and 0<=x1<M and grid[y1][x1]-grid[y][x]==D[d]:
for l in range(L):
DP[d+1][l][y1*M+x1] += DP[d][l][y*M+x]
return sum(map(sum,cal(DP[-1],k)))%mod
인접행렬 + DP 응용문제
풀이를 설명하면,
1. 각 좌표에 0~N*M-1까지 번호를 부여한다.
2. DP[d][n][m]은 n번에서 출발해서 d번 이동하여 m번에 도착하는 경우의 수를 의미한다. bottom-up 방식으로 DP를 채워준다.
3. D의 길이만큼 이동했을 때 n번에서 출발해서 m번에 도착하는 경우의 수 인접행렬을 구하였다. 이제 이를 k번 제곱하여 최종 경우의 수를 구한다. (분할정복을 이용해야한다)
인접행렬을 구할 때, 그냥 DFS로 구하려고 했다가 몇 가지 테스트 케이스에서 시간초과가 발생하였다. d의 크기가 최대 100이므로 DP를 활용하여야 시간초과가 발생하지 않게 된다.