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

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

프로그래머스

 

Status : Solved

 

Time : 01:14:18

 

---

 

문제 설명

 

 

현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다.

경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로 이동할 때 경사가 d[i]인 길을 지나야 함을 나타냅니다. 전기차가 경사로를 반복적으로 이동할 때 받는 스트레스를 관찰하기 위해 주어진 경사수열을 k번 반복할 수 있는 경로를 찾으려 합니다. 같은 칸을 여러 번 방문하거나 지나온 길을 바로 되돌아가는 경로도 가능합니다.

 

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

 

격자 칸의 높이를 담은 2차원 정수 배열 grid, 경사 수열을 담은 1차원 정수 배열 d와 경사 수열을 반복하는 횟수를 나타내는 정수 k가 매개변수로 주어집니다. 이때, 격자 내에서 조건을 만족하는 경로의 수를 return 하도록 solution 함수를 완성해 주세요. 단, 답이 커질 수 있으므로 1,000,000,007(= 10^9 + 7)로 나눈 나머지를 return 해주세요.

 

 

입력 및 출력

 

 

제한사항

 

• 3 ≤ grid의 길이 = n ≤ 8
• 3 ≤ grid[i]의 길이 = m ≤ 8
  • 0 ≤ grid[i][j] ≤ 1,000
  • grid[i][j]는 각자의 i+1번째 행, j+1번째 열에 위치한 칸의 높이를 나타냅니다.
• 1 ≤ d의 길이 ≤ 100
  • -100 ≤ d의 원소 ≤ 100
• 1 ≤ k ≤ 109

 

입출력 예

 

grid	d	k	result
[[3, 4, 6, 5, 3], [3, 5, 5, 3, 6], [5, 6, 4, 3, 6], [7, 4, 3, 5, 0]]	[1, -2, -1, 0, 2]	2	16
[[3, 6, 11, 12], [4, 8, 15, 10], [2, 7, 0, 16]]	[1, -2, 5]	3	1
[[0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1], [1, 0, 0]]	[0, 0, 1, -1, 0, 0, 1, -1]	10	595737277

 

 

---

 

풀이

 

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

풀이 완료!