[프로그래머스] 경사로의 개수 (Python)

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를 활용하여야 시간초과가 발생하지 않게 된다.