[ Lv 3 ] [ DP ] 보행자 천국

https://programmers.co.kr/learn/courses/30/lessons/1832

코딩테스트 연습 - 보행자 천국

 

---

풀이 과정

---

1. 4방향 모두 이동가능 하다면 DP로 풀이할 수 없지만 문제에서 오른쪽과 아래로만 이동 가능하다고 하였으므로 DP로 풀이 가능
2. 좌회전 / 우회전 금지가 없는 경우의 DP 점화식은 다음과 같다.
   1. DP[i][j] = DP[i][j-1] + DP[i-1][j]
3. 좌회전 / 우회전 금지가 존재하므로 해당 부분은 따로 처리해주어야 한다.
   1. 연속적으로 푯말이 있는 경우가 있으므로 해당 경우는 따로 처리해주어야 한다. 
   2. [i][j-1]에 금지 푯말이 있는 경우는 금지 푯말이 없을때까지 왼쪽으로 올라가보아야 함
   3. [i-1][j]에 금지 푯말이 있는 경우는 금지 푯말이 없을때까지 위로 올라가보아야 함
4. 경우의 수가 커질수도 있으므로 매순간 값을 구해준 다음 20170805의 나머지를 구해준다.
5. dp[m-1][n-1]을 리턴시켜 준다.

---

소스 코드

---

class Solution {
    int MOD = 20170805;

    public void calculateRowCell(int i, int j, int[][] cityMap, int[][] dp) {
        if (cityMap[i-1][j] == 2) {
            int dest = i-2;
            while (dest >= 0 && cityMap[dest][j] == 2)
                dest -= 1;
            if (dest >= 0)
                dp[i][j] += dp[dest][j];

        } else {
            dp[i][j] += dp[i-1][j];
        }
    }

    public void calculateColCell(int i, int j, int[][] cityMap, int[][] dp) {
        if (cityMap[i][j-1] == 2) {
            int dest = j-2;
            while (dest >= 0 && cityMap[i][dest] == 2)
                dest -= 1;
            if (dest >= 0)
                dp[i][j] += dp[i][dest];
        } else {
            dp[i][j] += dp[i][j - 1];
        }
    }

    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        int dp[][] = new int[m][n];
        dp[0][0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cityMap[i][j] == 1)
                    continue;
                if (i-1 >= 0) {
                    calculateRowCell(i, j, cityMap, dp);
                }
                if (j-1 >= 0) {
                    calculateColCell(i, j, cityMap, dp);
                }
                dp[i][j] %= MOD;
            }
        }
        answer = dp[m-1][n-1];
        return answer;
    }
}