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

문제

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

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

 

접근법

혼자서 DFS로 풀었다.

시간초과가 났다.

BFS로 풀려고 했다. 잘 풀리지 않았다.

결국엔 다른 사람이 짠 코드를 참고하여 dp로 풀었다.

최단 경로이기때문에 자동차는 오른쪽과 아래쪽으로 진행할 수 밖에 없다.

오른쪽으로 가는 경우의 수와 아래쪽으로 가는 경우의 수를 나눠 두 개의 배열로 만들었다.

rightArr 배열에는 오른쪽으로만 가는 경우의 수, downArr에는 아래쪽으로만 가는 경우의 수를 담았다.

최종 목적지에 도착하는 경우의 수는 최종 목적지 바로 왼쪽에서 오른쪽으로 향하는 경우와 바로 위쪽에서 아래쪽으로 향하는 경우 두 가지이다.

이 점을 고려해서 코드를 짰다.

 

코드

class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;

        int[][] rightArr = new int[m+1][n+1];
        int[][] downArr = new int[m+1][n+1];
        
        //첫 출발지 1로 초기화
        rightArr[1][1] = 1;
        downArr[1][1] = 1;

		
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //지나갈 수 있는 경우
                if(cityMap[i-1][j-1] == 0){
                    //바로 왼쪽에서 오른쪽으로 향하는 경우의 수와 바로 위쪽에서 아래쪽으로 향하는 경우의 수
                    //두 경우의 수를 더한 값이 현재 위치의 경우의 수
                    int cnt = (rightArr[i][j-1] + downArr[i-1][j]) % MOD;
                    rightArr[i][j] += cnt;
                    downArr[i][j] += cnt;
                //지나갈 수 없는 경우 0    
                }else if(cityMap[i-1][j-1] == 1){
                    rightArr[i][j] = 0;
                    downArr[i][j] = 0;
                //방향 전환을 할 수 없는 경우
                }else{
                    //바로 위쪽의 경우의 수를 그대로 넣고
                    downArr[i][j] = downArr[i-1][j];
                    //바로 왼쪽의 경우의 수를 그대로 넣는다.
                    rightArr[i][j] = rightArr[i][j-1];
                }
            }
        }

        answer = (downArr[m-1][n] + rightArr[m][n-1]) % MOD;
        return answer;
    }
}