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

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

---

 

경사가 1번 반복되는 경로의 수를 구해서 k번 반복되는 경로의 수를 구하면 되는 문제다.

1. 경사가 1번 반복되는 경로의 수 구하기

한 칸에서 다른 칸으로 폴짝 건너가는 것을 hop이라고 칭했다.
dp[startX][startY][endX][endY][hop]: (startX, startY)에서 시작하여 (endX, endY)까지 이동했을 때, d[0]~d[hop]까지의 경사를 만족하는 경로의 수

 

 

문제에서 주어진 예제를 예로 들어보자. d = [1, -2, -1, 0, 2]이다.

(1,1)부터 (2, 3)까지는 d[0]부터 d[2]까지의 경사 [-1, -2, -1]를 만족하는 경로의 수가 1개이다.

따라서 dp[1][1][2][3][2] = 1이 된다.

 

// long[][][][][] route;
// int[][][][][] dp;
// int N = grid.length, M = grid[0].length, K=1_000_000_007;
// int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

void findRoute(int x, int y, int hop, int[][] grid, int[] d) {
    for (int k=0; k<4; k++) {
        int nx = x+dx[k];
        int ny = y+dy[k];

        if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
        if(grid[nx][ny]-grid[x][y] != d[hop]) continue;
        if(hop==0) {
            dp[x][y][nx][ny][hop] = 1;
        } else {
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    dp[i][j][nx][ny][hop] += dp[i][j][x][y][hop-1];
                    dp[i][j][nx][ny][hop] %= K;
                }
            }
        }
    }
} 

for (int hop=0; hop<d.length; hop++) {
    // 모든 시작점에 대하여 반복
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            findRoute(i, j, hop, grid, d); 
        }
    }
}

for (int startX=0; startX<N; startX++) {
    for (int startY=0; startY<M; startY++) {
        for (int endX=0; endX<N; endX++) {
            for (int endY=0; endY<M; endY++) {
                route[startX][startY][endX][endY][0] = dp[startX][startY][endX][endY][d.length-1];
            }
        }
    }
}

 

dp를 이용하여 처음에는 경사 1개(d[0])만 만족하는 경로의 수를 찾고,
그 다음에는 2개(d[0], d[1])를 만족하는 경로의 수를 찾고,
이를 반복하다가 마지막엔 모든 경사를 만족하는 경로의 수를 찾으면 된다.

 

(BFS로 하면 메모리 초과가 발생한다.)

---

2. 경사가 k번 반복되는 경로의 수 구하기

경사가 1번 반복되는 경로의 수를 구했다. 경로가 2번 반복되는 경우의 수는 아래와 같다.

(시작점~도착점 경사 2번 반복되는 경로의 수) = (시작점~경유지 경사 1번 반복되는 경로의 수) * (경유지~도착점 경사 1번 반복되는 경로의 수)

 

(시작점~도착점 경사 3번 반복) = (시작점~경유지 경사 2번 반복) * (경유지~도착점 경사 1번 반복) 이므로

k = l+m일 때, (시작점~도착점 경사 k번 반복) = (시작점~경유지 경사 l번 반복) * (경유지~도착점 경사 m번 반복)이 된다.

 

이처럼 k번을 반복하면 답을 구할 수 있겠지만, k의 최댓값 = 10^9 이므로 시간초과가 날 확률이 매우 높다.

칸의 개수가 최대 64개이므로, (시작점, 경유지, 도착점) 쌍을 구하는 것만으로도 64*64*64 ≒ 10^6이기 때문이다.

그렇다면 어떻게 해야 할까?

 

(시작점~도착점 경사 1번 반복)을 이용해

(시작점~도착점 경사 2번 반복)

(시작점~도착점 경사 4번 반복)

.

.

.

(시작점~도착점 경사 2^n번 반복) 을 구한다.

 

for (int repeat = 1; repeat<str.length(); repeat++) {
    for (int start=0; start<N*M; start++) {
        int startX = start/M;
        int startY = start%M;

        for (int end=0; end<N*M; end++) {
            int endX = end/M;
            int endY = end%M;

            for (int stopOver=0; stopOver<N*M; stopOver++) {
                int stopOverX = stopOver/M;
                int stopOverY = stopOver%M;

                route[startX][startY][endX][endY][repeat] += (route[startX][startY][stopOverX][stopOverY][repeat-1]%K * route[stopOverX][stopOverY][endX][endY][repeat-1]%K)%K;
                route[startX][startY][endX][endY][repeat]%=K;
            }
        }
    }
}

 

 

그리고 k를 이진수로 표현한 뒤, 기존에 구해둔 2^n번 반복을 이용해 k번 반복되는 경로의 수를 구하면 된다.

예를 들어, k = 12 = 8 + 4라고 하면

(도착점까지 경사가 12번 반복되는 경로의 수) = (시작점까지 경로 8번 반복) * (시작점~도착점까지 경로 4번 반복)이 된다.

 

// StringBuilder sb = new StringBuilder(Integer.toBinaryString(k));
// String str = sb.reverse().toString();
// answer[i][j]: 현재까지 (i,j)를 도착점으로 삼는 경로의 수

void countRoute(String str) {
    for (int idx=0; idx<str.length(); idx++) {
        if(str.charAt(idx)=='0') continue;

        long[][] newAnswer = new long[N][M];

        for (int start=0; start<N*M; start++) {
            int startX = start/M;
            int startY = start%M;

            for (int end=0; end<N*M; end++) {
                int endX = end/M;
                int endY = end%M;

                newAnswer[endX][endY] += (answer[startX][startY]%K) * (route[startX][startY][endX][endY][idx]%K);
                newAnswer[endX][endY]%=K;
            }
        }

        answer = newAnswer;
    }

}

 

 

---

3. 정답 세기

그리고 마지막으로 모든 점에 대하여, 해당 점을 도착점으로 하는 경로의 수를 세어주면 된다.

long ans = 0;
        for (int endX=0; endX<N; endX++) {
            for (int endY=0; endY<M; endY++) {
                ans += (answer[endX][endY]%K);
                ans %= K;
            }
        }

 

---

전체 코드

 

import java.util.Arrays;

public class Programmers_경사로의개수 {
    long[][][][][] route;
    int[][][][][] dp;
    long[][] answer;
    int N, M, K=1_000_000_007;
    int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    public int solution(int[][] grid, int[] d, int k) {

        N = grid.length;
        M = grid[0].length;
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(k));
        String str = sb.reverse().toString();

        route = new long[N][M][N][M][str.length()];
        dp = new int[N][M][N][M][d.length];
        answer = new long[N][M];

        for (int i=0; i<N; i++) {
            Arrays.fill(answer[i], 1);
        }

        for (int hop=0; hop<d.length; hop++) {
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    findRoute(i, j, hop, grid, d);
                }
            }
        }

        for (int startX=0; startX<N; startX++) {
            for (int startY=0; startY<M; startY++) {
                for (int endX=0; endX<N; endX++) {
                    for (int endY=0; endY<M; endY++) {
                        route[startX][startY][endX][endY][0] = dp[startX][startY][endX][endY][d.length-1];
                    }
                }
            }
        }

        for (int repeat = 1; repeat<str.length(); repeat++) {
            for (int start=0; start<N*M; start++) {
                int startX = start/M;
                int startY = start%M;

                for (int end=0; end<N*M; end++) {
                    int endX = end/M;
                    int endY = end%M;

                    for (int stopOver=0; stopOver<N*M; stopOver++) {
                        int stopOverX = stopOver/M;
                        int stopOverY = stopOver%M;

                        route[startX][startY][endX][endY][repeat] += (route[startX][startY][stopOverX][stopOverY][repeat-1]%K * route[stopOverX][stopOverY][endX][endY][repeat-1]%K)%K;
                        route[startX][startY][endX][endY][repeat]%=K;
                    }
                }
            }
        }

        countRoute(str);

        long ans = 0;
        for (int endX=0; endX<N; endX++) {
            for (int endY=0; endY<M; endY++) {
                ans += (answer[endX][endY]%K);
                ans %= K;
            }
        }
        return (int) ans;
    }

    void findRoute(int x, int y, int hop, int[][] grid, int[] d) {
        for (int k=0; k<4; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];

            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(grid[nx][ny]-grid[x][y] != d[hop]) continue;
            if(hop==0) {
                dp[x][y][nx][ny][hop] = 1;
            } else {
                for (int i=0; i<N; i++) {
                    for (int j=0; j<M; j++) {
                        dp[i][j][nx][ny][hop] += dp[i][j][x][y][hop-1];
                        dp[i][j][nx][ny][hop] %= K;
                    }
                }
            }
        }
    }

    void countRoute(String str) {
        for (int idx=0; idx<str.length(); idx++) {
            if(str.charAt(idx)=='0') continue;

            long[][] newAnswer = new long[N][M];

            for (int start=0; start<N*M; start++) {
                int startX = start/M;
                int startY = start%M;

                for (int end=0; end<N*M; end++) {
                    int endX = end/M;
                    int endY = end%M;

                    newAnswer[endX][endY] += (answer[startX][startY]%K) * (route[startX][startY][endX][endY][idx]%K);
                    newAnswer[endX][endY]%=K;
                }
            }

            answer = newAnswer;
        }

    }
}