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

Problem : https://school.programmers.co.kr/learn/courses/30/lessons/214290

프로그래머스

 

Status : Solved

 

Time : 01:14:18

 

---

 

문제 설명

 

문제 및 예시는 위 링크를 참조해주세요!

 

입력 및 출력

자세한 예시는 링크를 참조해 주세요!

---

 

풀이

 

1. 조건에 맞는 패턴 d를 가지는 경로를 어떻게 찾을 것인가? 단순한 경로탐색으로 풀이한다면 시간초과를 겪을 수밖에 없다. 왔던 길을 되돌아갈 수 있으므로 가능한 경우의 수가 기하급수적으로 커지기 때문이다. 하지만 현재 경로, 현재 패턴 idx, 그리고 도달하는 최종 경로를 기준으로 생각한다면 전체 문제를 부분 문제로 쪼갤 수 있음을 쉽게 눈치챌 수 있다. 따라서 DP를 고려하고 문제를 풀이해야 한다.

 

 

2. 두 번째. 반복횟수 k가 최대 10의 9승까지도 이어질 수 있다. 그렇다면 단순한 선형 시간으로 문제를 접근해서는 안된다. 다시 돌아가서, 1번의 DP에 저장될 최종 정보를 떠올려보자. (시작 좌표, 끝 좌표)에 (패턴 d로 이어지는 경우의 수)가 저장되므로, 이를 하나의 행렬로 볼 수 있다.

 

2022.11.29 - [알고리즘 문제/CodeUp] - [CodeUp/2753] 수열의 n번째 항 (Python)

[CodeUp/2753] 수열의 n번째 항 (Python)

 

즉 패턴을 n회 반복하는 경우 이 행렬의 n 거듭제곱을 참조해 볼 수 있다. 1번째 시작좌표 - 1번째 끝좌표 - 2번째 끝좌표 - ... - n번째 끝좌표로 이어지는 모든 경우의 수를 구하는 경우와 같기 때문이다. 즉 이 최대 64 x 64 행렬을 k제곱하는 게 첫 번째이며, 이를 앞선 문제처럼 분할정복 방식으로 구현한다면 O(logk)시간 내에 결과를 구할 수 있다.

 

3. 1, 2를 거친 행렬의 모든 요소의 합이 정답이 된다.

 

풀이 코드

from collections import defaultdict

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
MOD = 1000000007

def matmul(mat1, mat2) :
    result = [[0]*L for _ in range(L)]
    for i in range(L) :
        for j in range(L) :
            for k in range(L) :
                result[i][j] = (result[i][j] + mat1[i][k] * mat2[k][j] ) % MOD
    return result

def matpow(mat, k) :
    if k == 1 :
        return mat
    p = matpow(mat, k // 2)
    p = matmul(p, p)
    if k % 2 :
        return matmul(p, mat)
    else :
        return p

def dfs(grid, d, r, c, idx, dp) :
    global R, C
    coord = r*C + c
    if idx == len(d) :
        return { coord : 1 }
    
    if dp[idx][coord] :
        return dp[idx][coord]
    
    for k in range(4) :
        ar, ac = r + dr[k], c + dc[k]
        if -1 < ar < R and -1 < ac < C and grid[ar][ac] - grid[r][c] == d[idx] :
            result = dfs(grid, d, ar, ac, idx+1, dp)
            for key, val in result.items() :
                dp[idx][coord][key] = ( dp[idx][coord][key] + val ) % MOD
    return dp[idx][coord]
        
def find_pattern(grid, d, k) :
    dp = [[defaultdict(int) for _ in range(L)] for _ in range(len(d))]
    for r in range(R) :
        for c in range(C) :
            dfs(grid, d, r, c, 0, dp)
            
    mat = [[dp[0][i][j] % MOD for j in range(L)] for i in range(L)]
    mat = matpow(mat, k)
    answer = 0
    for i in range(L) :
        for j in range(L) :
            answer = (answer + mat[i][j]) % MOD

    return answer

def solution(grid, d, k):
    global R, C, L
    R, C = len(grid), len(grid[0])
    L = R*C
    answer = find_pattern(grid, d, k)
    return answer

풀이 완료!