[프로그래머스] 보행자 천국

문제 설명

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

문제 풀이

• 간단한 DFS + DP 문제였다
• Bottom-Up 방식으로 구현하였는데 그나마 특별한 점은 DP배열을 DP[X][Y]가 아닌 DP[X][Y][들어온방향]으로 구성해줘야 한다는 점이다.
• 이유는, 2번 블록 때문에 위에서 올때와 왼쪽에서 올때의 다음 진행 차이가 있기 때문이다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int MOD = 20170805;
    public int M, N;
    public int[][] map;
    public int[][][] dp;
    public int[] dx = {0, 1};
    public int[] dy = {1, 0};

    public int solve(int x, int y, int beforeD) {
        //기저 조건
        if (x == M-1 && y == N-1) return 1;
        if (dp[x][y][beforeD] != -1) return dp[x][y][beforeD];

        int result = 0;
        for (int d = 0; d < 2; d++) {
            int X = x + dx[d];
            int Y = y + dy[d];
            if (X >= M || Y >= N) continue;
            if (map[X][Y] == 1) continue;
            if (map[x][y] == 2 && beforeD != d) continue;
            result = (result + solve(X, Y, d)) % MOD;
        }
        return dp[x][y][beforeD] = result;
    }

    public int solution(int m, int n, int[][] cityMap) {
        //초기화
        M = m;
        N = n;
        map = cityMap;
        dp = new int[M][N][2];
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(dp[i][j], -1);
        return solve(0, 0, 0);
    }
}