EunSung.log

보행자 천국

3 min read

문제 정보

풀이

일반적인 경로의 수 문제와 달리

  1. 통행이 불가능한 칸이 있고 (등굣길 문제처럼)
  2. 진행 방향이 정해지는 칸이 있다.

특히 2번 사항 때문에 위에서 내려왔는지, 왼쪽에서 왔는지에 따라 경우의 수가 달라진다. 그렇기 때문에 상태를 2개로 가져가야 한다.

  • dp[i][j][0]: (i, j) 칸에 위에서 내려온 경우의 수
  • dp[i][j][1]: (i, j) 칸에 왼쪽에서부터 온 경우의 수

cityMap[i - 1][j - 1]이1

  • 0인 경우: 자유롭게 통행이 가능하므로
    • dp[i][j][0] = (dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
    • dp[i][j][1] = (dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
  • 1인 경우: 통행할 수 없으므로 스킵
  • 2인 경우: 한 쪽으로만 다닐 수 있으므로
    • dp[i][j][0] = dp[i - 1][j][0];
    • dp[i][j][1] = dp[i][j - 1][1];

마지막으로, cityMap[m - 1][n - 1]은 항상 0이다. 즉 앞선 점화식에 따르면 dp[m][n][0]과 dp[m][n][1]은 항상 같은 값을 가진다. 따라서 둘 중 아무 값이나 반환해도 된다.

코드

import java.util.*;
 
class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int[][][] dp = new int[m + 1][n + 1][2];
        
        dp[1][1][0] = 1;
        dp[1][1][1] = 1;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (cityMap[i - 1][j - 1] == 1) continue;
                
                if (cityMap[i - 1][j - 1] == 0) {
                    dp[i][j][0] += (dp[i - 1][j][0] + dp[i][j - 1][1]) %  MOD;
                    dp[i][j][1] += (dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
                } else {
                    dp[i][j][0] = dp[i - 1][j][0];
                    dp[i][j][1] = dp[i][j - 1][1];
                }
            }
        
        }
        return dp[m][n][0];
    }
}

Footnotes

  1. 1-based 인덱스를 사용했을 때. (경계값 처리를 없애기 위함) ↩

백링크