[프로그래머스] 카카오_보행자 천국 (자바 풀이)

문제

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

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

 

 

풀이

정말 어려웠지만 재밌는 문제였다. 풀이법이 잘 생각나지 않지만 생각만 잘한다면 코드 길이가 매우 짧고 명료하게 해결할 수 있다.

 

이 문제는 DP를 이용하면 해결할 수 있다. 

 

나는 DP 배열을 다음과 같이 정의했다.

 

DP[0][i][j] = (i,j) 좌표에 세로로 들어오는 경우의 수

DP[1][i][j] = (i, j) 좌표에 가로로 들어오는 경우의 수

 

또한, 점화식을 다음과 같이 설정하면 된다.

 

1) cityMap[i][j] == 0 인 경우 -> 오른쪽 혹은 아래로 진입 가능

 

DP[0][i+1][j] += (DP[0][i][j] + DP[1][i][j] ) % MOD -> 세로 방향으로 (i, j)에 들어왔을때와 가로 방향으로 (i,j)에 들어왔을 때

두 방향 모두 (i+1, j)로 이동 가능 하므로 두 경우의 수를 더해 준다.

 

 

 DP[1][i][j+1] += (DP[0][i][j] + DP[1][i][j] ) % MOD -> 세로 방향으로 (i, j)에 들어왔을 때와 가로 방향으로 (i, j)에 들어왔을 때

두 방향 모두 (i, j+1)로 이동 가능 하므로 두 경우의 수를 더해 준다.

 

2) cityMap[i][j] == 1 인 경우

 

어느 쪽으로도 이동할 수 없으므로 신경 쓰지 않아도 된다.

 

3) cityMap[i][j] == 2 인 경우 -> 전에 들어왔던 방향으로만 움직일 수 있다.

 

DP[0][i+1][j] += DP[0][i][j] % MOD -> 이전에 세로 방향으로 들어온 경우만 이동할 수 있다.

DP[1][i][j+1] += DP[1][i][j] % MOD -> 이전에 가로 방향으로 들어온 경우만 이동할 수 있다.

 

따라서 마지막에 (DP[0][m-1][n-1] + DP[1][m-1][n-1] )%MOD 를 반환해주면 정답이다!

 

 

코드

import java.util.*;

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