[프로그래머스/Java] 경사로의 개수 - Lv. 4 문제 풀이

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

프로그래머스

 

2023년 현대 모비스 알고리즘 경진대회 예선 문제라고 한다.

현대 모비스에서 소프트웨어를 강조하기 위해 주최하는 경진대회라고 하는데 어마어마한 상품으로 상당히 화제였었다.

1위 상이 무려 아이오닉 5... 차 한대가 상품이었다.

2등상은 1,000만원 3등상은 500만원으로 역대급 대회였다.

 

하지만 그런 만큼 진짜 쟁쟁하신 분들이 나오셨다고...

2024년 현대 모비스 알고리즘 경진대회도 총 상금 1억 7천만원이 걸려 있고, 프로그래머스에서 6월 25일까 접수받고 있다.

=> 2024년 현대 모비스 알고리즘 경진대회 접수

 

어쨌든 이 문제는 프로그래머스에서 Lv4로 등재되었고, 2차원 배열과 이동 가능한 조건이 주어졌을 때, 이동 가능한 경로의 개수를 찾는 문제이다.

 

문제 전문 ↓

문제 설명

현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 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(= 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 ≤ 10^9

입출력 예

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 하면 됩니다.

문제 풀기

제한 사항으로 접근법 떠올려보기

문제에서 주어진 제한 사항은 다음과 같습니다.

• 3 ≤ grid의 길이 = n ≤ 8
• 3 ≤ grid[i]의 길이 = m ≤ 8
• 0 ≤ grid[i][j] ≤ 1,000
• 1 ≤ d의 길이 ≤ 100
• 1 ≤ k ≤ 10^9

그리드의 크기는 작은 반면, k의 크기는 10억으로 매우 크다는 것을 알 수 있습니다.

k는 d를 반복해야 하는 횟수이므로 k번에 해당하는 만큼 반복을 해야 할 것 같기는 한데, 그 값을 보니 k번 반복을 해서는 안됩니다.

 

그렇다면 log의 시간 복잡도를 가지는 분할 정복을 떠올릴 수 있습니다.

k를 반으로 나눠가며 연산하는 분할 정복이라면 O(logK)번 만에 k번에 해당하는 반복을 계산해낼 수 있을 것입니다.

 

이제 문제를 분할 정복에 맞도록 정의할 수 있는지를 확인하면 됩니다.

부분 문제 정의하기

주어진 문제를 분할 정복을 활용해 k번 반복되는 부분 문제로 만들어야 합니다.

문제에서 k번 반복되는 것은 d를 적용하는 횟수입니다.

따라서 d를 적용하는 횟수의 가장 최소 횟수인 1인 문제를 먼저 풀고, 이를 k번 반복하는 것으로 접근할 수 있습니다.

(x1, y1, x2, y2): (x1, y1)에서 (x2, y2)로 d를 이용하여 이동하는 경로의 수

(x1, y1, x2, y2)는 제 책 [취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략: 자바편]에서 소개한 문제를 나타내기 위한 표기법으로, 문제를 정의하기 위해 필요한 변수의 집합이라고 생각하시면 됩니다.

더 작은 부분 문제

그런데 위의 문제를 풀기 위해서는 경로를 파악해야 합니다.

이는 다시 부분 문제를 정의하여 다음과 같이 재귀적으로 해결할 수 있습니다.

(x1, y1, x2, y2, di): (x1, y1)에서 (x2, y2)로 d[di]~d[끝]을 이용해서 갈 수 있는 경우의 수
                            = (x1, y1, x, y, i) * (x, y, x2, y2, d.length - i) => 모든 x, y와 di <= i <= d.length에 대한 반복 합

 

(x1, y1, x2, y2, di)를 풀면, (x1, y1, x2, y2) = (x1, y1, x2, y2, 0)으로 구할 수 있게 됩니다.

 

이 부분에 해당하는 코드 ↓

private static final int DIV = 1_000_000_007;
private static final int[] dx = {1, 0, -1, 0};
private static final int[] dy = {0, 1, 0, -1};

private static int count(
    int x1, int y1, int x2, int y2, int di, int[][] grid, int[] d, int[][][][][] mem) {
  // Memoization
  if (mem[di][x1][y1][x2][y2] != -1) {
    return mem[di][x1][y1][x2][y2];
  }
  
  // 종료 조건
  if (di == d.length) {
    if (x1 == x2 && y1 == y2) {
      return mem[di][x1][y1][x2][y2] = 1;
    } else {
      return mem[di][x1][y1][x2][y2] = 0;
    }
  }
  
  // 재귀
  int sum = 0;
  for (int i = 0; i < 4; i++) {
    int nx = x1 + dx[i];
    int ny = y1 + dy[i];
    try {
      if (grid[ny][nx] == grid[y1][x1] + d[di]) {
        sum += count(nx, ny, x2, y2, di + 1, grid, d, mem);
        sum %= DIV;
      }
    } catch (IndexOutOfBoundsException ignored) {
    }
  }
  return sum;
}

private static int[][][][] buildCountMatrix(int[][] grid, int[] d) {
  int w = grid[0].length;
  int h = grid.length;
  
  // [i][x1][y1][x2][y2]: (x1, y1) -> (x2, y2)를 d[i] ~ d[끝]을 이용해 갈 수 있는 경우의 수
  int[][][][][] mem = new int[d.length + 1][w][h][w][h];
  
  for (int di = d.length; di >= 0; di--) {
    for (int x1 = 0; x1 < w; x1++) {
      for (int y1 = 0; y1 < h; y1++) {
        for (int x2 = 0; x2 < w; x2++) {
          Arrays.fill(mem[di][x1][y1][x2], -1);
          for (int y2 = 0; y2 < h; y2++) {
            mem[di][x1][y1][x2][y2] = count(x1, y1, x2, y2, di, grid, d, mem);
          }
        }
      }
    }
  }
  return mem[0];
}

부분 문제 시간 복잡도

(x1, y1, x2, y2, di)의 경우 재귀가 진행됨에 따라 반복되는 부분 문제이기 때문에 한 단계의 상태를 구하기 위한 시간 복잡도와 상태의 개수를 이용해 시간 복잡도를 계산할 수 있습니다.

 

하나의 상태를 구하기 위해서는 d의 길이만큼 반복하고, x, y에 대해서도 반복합니다.

• 1 <= d의 길이 <= 100
• 3 <= x, y, <= m = 8

주어진 조건이 위와 같으므로시간 복잡도는 O(dm²)이 되고, 최댓값을 대입했을 때 6,400이므로 이 부분 문제는 충분한 시간 복잡도를 가지고 있음을 알 수 있습니다.

분할 정복

(x1, y1, x2, y2)를 해결할 수 있으니, 이를 이용해 k번 반복하는 문제를 해결해야 합니다.

이 문제는 다음과 같이 정의할 수 있습니다.

(x1, y1, x2, y2, r): (x1, y1)에서 (x2, y2)로 d를 r번 이용하여 이동하는 경우의 수
                           = (x1, y1, x, y, r / 2) * (x, y, x2, y2, r / 2) => r이 짝수일 경우
                           = (x1, y1, x, y, r / 2) * (x, y, x2, y2, r / 2) * (x1, y1, x2, y2, 1) => r이 홀수일 경우
(x1, y1, x2, y2, 1) = (x1, y1, x2, y2)

 

모든 x1, y1, x2, y2에 대해 이를 반복한다면 답을 구할 수 있습니다.

 

그런데 문제가 있습니다. 이 부분 문제는 메모이제이션을 적용할 수 없다는 것입니다.

r의 크기는 최대 10억으로, 이는 메모이즈하기에는 너무 큰 값입니다.

 

모든 출발점과 도착점에 대해서 같은 연산을 해야 한다는 점을 생각하면 비슷하지만 조금 다른 접근 방식을 생각할 수 있습니다.

행렬 연산

한 점에서 다른 점으로 이동하는 경로의 수는 행렬로 표현할 수 있습니다.

사실, 이미 행렬로 표현되어 있습니다.

문제 (x1, y1, x2, y2)가 풀어낸 답이 바로 그 행렬입니다.

 

이 문제의 결과는 [x1, y1, x2, y2]의 4차원 배열이 됩니다.

이 배열의 각 원소는 (x1, y1)에서 (x2, y2)로 이동할 수 있는 경로의 수를 가지고 있습니다.

 

지금 우리가 구해야 하는 것은 (x1, y1)에서 출발하고, (x2, y2)에 도착하지만, 그 과정 중에 어떠한 좌표 (x, y)를 경유하면서 이동하는 경우의 수입니다.

 

이는 행렬의 곱셈과 같습니다. 즉, 행렬을 k번 거듭제곱하는 것으로 모든 좌표에 대해 같은 연산을 적용할 수 있게 됩니다.

 

이 부분에 해당하는 코드 ↓

private int[][][][] multiply(int[][][][] a, int[][][][] b) {
  int w = a.length;
  int h = a[0].length;
  
  int[][][][] m = new int[w][h][w][h];
  for (int x1 = 0; x1 < w; x1++) {
    for (int y1 = 0; y1 < h; y1++) {
      for (int x2 = 0; x2 < w; x2++) {
        for (int y2 = 0; y2 < h; y2++) {
          for (int x = 0; x < w; x++) {
            for (int y = 0; y < h; y++) {
              m[x1][y1][x2][y2] += (int) (((long) a[x1][y1][x][y] * b[x][y][x2][y2]) % DIV);
              m[x1][y1][x2][y2] %= DIV;
            }
          }
        }
      }
    }
  }
  return m;
}

private int[][][][] power(int[][][][] matrix, int power) {
  if (power == 1) {
    return matrix;
  }
  if (power == 2) {
    return multiply(matrix, matrix);
  }
  
  int[][][][] result = power(power(matrix, power / 2), 2);
  if (power % 2 == 1) {
    result = multiply(result, matrix);
  }
  return result;
}

행렬 연산 시간 복잡도

한 번의 재귀 단계에 x1, y1, x2, y2, x, y에 대해서 반복합니다.

반복의 깊이는 log k이므로 전체 시간 복잡도는 O(log k * m^6)이 됩니다.

마무리

이제 결과 행렬에서 모든 원소를 순회하며 경로의 개수 합을 구해주면 됩니다.

 

이 부분에 해당하는 코드 ↓

public int solution(int[][] grid, int[] d, int k) {
  int[][][][] matrix = buildCountMatrix(grid, d);
  matrix = power(matrix, k);
  
  int count = 0;
  
  int w = matrix.length;
  int h = matrix[0].length;
  
  //noinspection ForLoopReplaceableByForEach Suppress for better readability.
  for (int x1 = 0; x1 < w; x1++) {
    for (int y1 = 0; y1 < h; y1++) {
      for (int x2 = 0; x2 < w; x2++) {
        for (int y2 = 0; y2 < h; y2++) {
          count += matrix[x1][y1][x2][y2] % DIV;
          count %= DIV;
        }
      }
    }
  }
  
  return count;
}

전체 시간 복잡도

전체 풀이는 다음의 단계를 따라갑니다.

1. (x1, y1, x2, y2, di)를 해결하는 부분
   • 시간 복잡도: O(dm²)
2. 행렬의 거듭제곱을 계산하는 부분
   • 시간 복잡도: O(log k * m^6)
3. 경로 합을 구하는 부분
   • 시간 복잡도: O(m⁴)

따라서 전체 시간 복잡도는 O(dm²) + O(log k * m^6) + O(m⁴) = O((d + log k * m⁴)m²)이 되고,

최댓값을 고려했을 때 d < log k * m⁴d이므로 O(log k * m^6)이 됩니다.

 

제한 사항을 고려해 최댓값을 대입하면 약 784만이라는 값이 나와, 충분한 시간 복잡도라는 것을 알 수 있습니다.

전체 코드

import java.util.Arrays;

public class Solution {
  private static final int DIV = 1_000_000_007;
  private static final int[] dx = {1, 0, -1, 0};
  private static final int[] dy = {0, 1, 0, -1};

  private static int count(
      int x1, int y1, int x2, int y2, int di, int[][] grid, int[] d, int[][][][][] mem) {
    // Memoization
    if (mem[di][x1][y1][x2][y2] != -1) {
      return mem[di][x1][y1][x2][y2];
    }

    // 종료 조건
    if (di == d.length) {
      if (x1 == x2 && y1 == y2) {
        return mem[di][x1][y1][x2][y2] = 1;
      } else {
        return mem[di][x1][y1][x2][y2] = 0;
      }
    }

    // 재귀
    int sum = 0;
    for (int i = 0; i < 4; i++) {
      int nx = x1 + dx[i];
      int ny = y1 + dy[i];

      try {
        if (grid[ny][nx] == grid[y1][x1] + d[di]) {
          sum += count(nx, ny, x2, y2, di + 1, grid, d, mem);
          sum %= DIV;
        }
      } catch (IndexOutOfBoundsException ignored) {
      }
    }
    return sum;
  }

  private static int[][][][] buildCountMatrix(int[][] grid, int[] d) {
    int w = grid[0].length;
    int h = grid.length;

    // [i][x1][y1][x2][y2]: (x1, y1) -> (x2, y2)를 d[i] ~ d[끝]을 이용해 갈 수 있는 경우의 수
    int[][][][][] mem = new int[d.length + 1][w][h][w][h];

    for (int di = d.length; di >= 0; di--) {
      for (int x1 = 0; x1 < w; x1++) {
        for (int y1 = 0; y1 < h; y1++) {
          for (int x2 = 0; x2 < w; x2++) {
            Arrays.fill(mem[di][x1][y1][x2], -1);
            for (int y2 = 0; y2 < h; y2++) {
              mem[di][x1][y1][x2][y2] = count(x1, y1, x2, y2, di, grid, d, mem);
            }
          }
        }
      }
    }

    return mem[0];
  }

  private int[][][][] multiply(int[][][][] a, int[][][][] b) {
    int w = a.length;
    int h = a[0].length;

    int[][][][] m = new int[w][h][w][h];
    for (int x1 = 0; x1 < w; x1++) {
      for (int y1 = 0; y1 < h; y1++) {
        for (int x2 = 0; x2 < w; x2++) {
          for (int y2 = 0; y2 < h; y2++) {
            for (int x = 0; x < w; x++) {
              for (int y = 0; y < h; y++) {
                m[x1][y1][x2][y2] += (int) (((long) a[x1][y1][x][y] * b[x][y][x2][y2]) % DIV);
                m[x1][y1][x2][y2] %= DIV;
              }
            }
          }
        }
      }
    }
    return m;
  }

  private int[][][][] power(int[][][][] matrix, int power) {
    if (power == 1) {
      return matrix;
    }
    if (power == 2) {
      return multiply(matrix, matrix);
    }

    int[][][][] result = power(power(matrix, power / 2), 2);
    if (power % 2 == 1) {
      result = multiply(result, matrix);
    }

    return result;
  }

  public int solution(int[][] grid, int[] d, int k) {
    int[][][][] matrix = buildCountMatrix(grid, d);
    matrix = power(matrix, k);

    int count = 0;

    int w = matrix.length;
    int h = matrix[0].length;

    //noinspection ForLoopReplaceableByForEach Suppress for better readability.
    for (int x1 = 0; x1 < w; x1++) {
      for (int y1 = 0; y1 < h; y1++) {
        for (int x2 = 0; x2 < w; x2++) {
          for (int y2 = 0; y2 < h; y2++) {
            count += matrix[x1][y1][x2][y2] % DIV;
            count %= DIV;
          }
        }
      }
    }

    return count;
  }
}