Java - [프로그래머스]1832 - Lv3.보행자 천국

출처

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

프로그래머스

 

문제

 

주어진 도로 상태의 상태에 따라, 목적지 까지 도착 가능한 전체 경로 수를 구하는 문제이다.

 

문제에 최단 경로라고 명시되어 있지는 않지만, 오른쪽 또는 아래 방향으로 이동 가능하다고 되어있기 때문에 최단 경로를 구하는 문제가 맞다. 보통 지도가 주어지고 최단 경로의 수를 구하려면 오른쪽 또는 아래 방향으로만 이동 가능하다고 가정하고 푼다. (왼쪽 지점과 위 지점 경우의 수를 더함)

 

풀이

처음에는 문제를 제대로 읽지 않아, 최단경로 인줄 모르고 dfs를 이용해 풀었다. 테스트 케이스에서는 통과하였지만, 채점 결과 시간 초과가 떴었다.

 

다시 문제를 제대로 읽고 나서, 최단 경로를 구하는 문제인 줄 알았다. 그래서  최단경로를 구할때 DP로 구하기 때문에 DP로 해결하였다.

 

하지만 조건이 있다. 만약 상태가 2인 경우에는 진행하던 방향을 바꿀 수 없다는 조건이다. 따라서 기존 경우의 수를 기록함과 동시에 방향을 기록해 놓기 위해 3차원 배열의 dp를 선언하여 해결하였다. (왼쪽, 위 정보를 추가)

 

핵심은, 왼쪽 지점의 정보를 가져올 때 상태가 2라면 dp[i][j-1][left] 만 가져와야 하고 만약 상태가 0이라면 추가로dp[i][j-1][up]을 더해서 기록한다는 점이다. (왼쪽 지점에서 좌회전 해서 온 정보를 기록하지 않음). 위쪽 정보도 동일하게 생각하여 해결하면 된다.

 

아래 코드를 보면 더 잘 이해가 될 것이다.

 

코드

import java.util.*;

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