[level 4] 경사로의 개수 - 214290

문제 링크

문제 설명

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

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

예를 들어 아래와 같은 격자에서 경사 수열 d = [1, -2, -1, 0, 2]이고 k = 2라고 가정해 보겠습니다. 이 경사 수열을 k = 2 번 반복할 수 있는 경로 중 하나는 아래 그림과 같습니다.

위 경로에서 방문한 칸의 높이는 방문 순서대로 [5, 6, 4, 3, 3, 5, 6, 4, 3, 3, 5]입니다. 길의 경사가 순서대로 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]으로, d가 2번 반복되었습니다.

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

문제 예시와 같습니다. 조건을 만족하는 경로의 수는 16가지가 있습니다.
따라서 16을 return 하면 됩니다.

입출력 예 #2

조건을 만족하는 경로의 수는 1가지가 있습니다.
따라서 1을 return 하면 됩니다.

입출력 예 #3

조건을 만족하는 경로의 수는 8,160,249,293,367,222,249,455,616 가지가 있습니다.
따라서 경로의 수를 109 + 7로 나눈 나머지인 595737277을 return 하면 됩니다.

코드 보기

#include <iostream>
#include <vector>

using namespace std;

// 두 행렬을 곱하는 함수 선언
vector<vector<long long>> mulMatrix(const vector<vector<long long>>& a, const vector<vector<long long>>& b, int n);

// 상수 선언
const int MOD = 1000000007; // 나머지 연산을 위한 모듈러 값
const int dx[] = {1, 0, -1, 0}; // x축 이동에 대한 방향 벡터
const int dy[] = {0, 1, 0, -1}; // y축 이동에 대한 방향 벡터

// 주어진 조건에 따라 가능한 경로 수를 계산하는 함수
int solution(vector<vector<int>> grid, vector<int> d, int k) {
    int n = grid.size(); // 그리드의 행 개수
    int m = grid[0].size(); // 그리드의 열 개수
    int dl = d.size(); // d 배열의 크기

    // 다이나믹 프로그래밍을 위한 3차원 벡터 초기화
    vector<vector<vector<long long>>> dp(dl + 1, vector<vector<long long>>(n * m, vector<long long>(n * m, 0)));

    // 기저 상태 초기화
    for (int i = 0; i < n * m; i++) 
    {
        dp[0][i][i] = 1;
    }

    // 다이나믹 프로그래밍으로 각 상태 계산
    for (int l = 1; l <= dl; l++)
    {
        for (int i = 0; i < n * m; i++) 
        {
            int x = i % m; // 현재 위치의 x 좌표
            int y = i / m; // 현재 위치의 y 좌표

            for (int dir = 0; dir < 4; dir++) // 4가지 방향에 대해 반복
            {
                int nx = x + dx[dir]; // 새로운 x 좌표
                int ny = y + dy[dir]; // 새로운 y 좌표

                // 그리드 경계 및 조건 검사
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[ny][nx] - grid[y][x] != d[l - 1]) {
                    continue;
                }

                // 다음 상태로의 전이
                for (int j = 0; j < n * m; j++) {
                    dp[l][j][ny * m + nx] += dp[l - 1][j][i] % MOD;
                    dp[l][j][ny * m + nx] %= MOD;
                }
            }
        }
    }

    // 이진 지수 승을 위한 카운트 계산
    int count = 0;
    while ((1 << count) < k) 
    {
        count++;
    }

    // 지수 승 계산을 위한 에지 파워 벡터 초기화 및 계산
    vector<vector<vector<long long>>> edgePower(count + 1, vector<vector<long long>>(n * m, vector<long long>(n * m, 0)));
    edgePower[0] = dp[dl];
    for (int c = 1; c <= count; c++) 
    {
        edgePower[c] = mulMatrix(edgePower[c - 1], edgePower[c - 1], n * m);
    }

    // 결과를 저장할 행렬 초기화
    vector<vector<long long>> mat(n * m, vector<long long>(n * m, 0));
    for (int i = 0; i < n * m; i++) 
    {
        mat[i][i] = 1;
    }

    // k번 이동에 대한 최종 결과 계산
    int kNum = k;
    while (kNum > 0) 
    {
        if (kNum >= (1 << count)) 
        {
            mat = mulMatrix(mat, edgePower[count], n * m);
            kNum -= (1 << count);
        }
        count--;
    }

    // 결과값 계산 및 반환
    long long answer = 0;
    for (int i = 0; i < n * m; i++) 
    {
        for (int j = 0; j < n * m; j++) 
        {
            answer += mat[i][j];
            answer %= MOD;
        }
    }

    return static_cast<int>(answer);
}

// 두 행렬을 곱하는 함수 구현
vector<vector<long long>> mulMatrix(const vector<vector<long long>>& a, const vector<vector<long long>>& b, int n) 
{
    vector<vector<long long>> result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            for (int k = 0; k < n; k++) 
            {
                result[i][j] = (result[i][j] + ((a[i][k] * b[k][j]) % MOD)) % MOD;
            }
        }
    }
    return result;
}

구현 결과