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

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

프로그래머스

[문제 설명]

 

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

• 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
• 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
• 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

예제 입출력

m	n	city_map	answer
3	3	[[0, 0, 0], [0, 0, 0], [0, 0, 0]]	6
3	6	[[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]]	2

예제에 대한 설명

첫 번째 예제는 모든 도로가 제한 없이 통행 가능한 경우로, 가능한 경우의 수는 6가지이다.
두 번째 예제는 문제 설명에 있는 그림의 경우이다. 가능한 경우의 수는 빨간 실선과 노란 점선 2가지뿐이다.

 

[풀이]

얼마 전에 해결했던 https://tosuccess.tistory.com/45 (등굣길) 문제와 흡사하니 혹시 먼저 보실 분들은 보시길 추천한다.

dp를 이용해 문제를 해결했다. 직진 구간에서는 그 구간을 계산하지 않고 일단 -5라는 값으로 임시 배분했고, 막힌 구간은 아예 계산하지 않는다. 최소거리를 구하려면 어떠한 지점에서 왼쪽, 위 구간의 수를 자신의 지점에 더해줘야 하는데 이 문제 같은 경우는 직진 구간이 있어서 그 부분을 따로 계산해줘야 했다. 즉 위쪽 길이 그냥 길or직진, 왼쪽에서 오는 길이 그냥 길or직진인가를 파악해줬다.

 

[코드]

int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int[][] dp = new int [m+1][n+1];        //실제 반환되는 dp배열
        int[][] answer = new int[m+1][n+1];        //cityMap에서 어느 부분이 장애물이 있나 확인하는 배열
        for(int i = 0; i< m; i++) {                //배열 초기화
            for(int j = 0; j < n; j++) {
                if(cityMap[i][j] == 1)             //1을 -1로
                    answer[i+1][j+1] = -1;        //2를 -2로
                else if(cityMap[i][j] == 2) 
                    answer[i+1][j+1] = -2;
                else 
                    answer[i+1][j+1] =cityMap[i][j]; 
            }
        }
        
        dp[1][1] = 1;                            //시작부분을 1로 초기화
        for(int i = 1; i <= m; i++) {            
            for(int j= 1; j <=n; j++) {
                if(answer[i][j] == -1) {            //금지면 0이므로
                    continue;
                }
                if(answer[i][j] == -2) {            //직진 구역을 -5로 표시
                    dp[i][j] = -5;
                    continue;
                }
                
                if(i == 1) {                //첫줄
                    if(dp[i][j-1] != -5) {    //-5가 아니면 전 값 추가
                        dp[i][j] += dp[i][j-1] %MOD;
                    }else {
                        for(int s = j -2; j >= 1; s--) {  //만약 계속 -5라면 아닐때까지 반복해서 아닌 값 추가.(직진 구역이 여러곳 있을 수 있으므로)
                            if(dp[i][s] != -5) {
                                dp[i][j] += dp[i][s] %MOD;
                                break;
                            }
                        }
                    }
                    
                }else {                            //첫번째 줄이 아닌 경우
                    if(dp[i][j-1] != -5) {
                        //왼쪽에서 오는길이 직진이 아님
                        dp[i][j] += dp[i][j-1] %MOD;
                    }else {
                        //왼쪽에서 오는길이 직진임.
                        for(int s = j-2; s >=1; s--) {
                            if(dp[i][s] != -5) {
                                dp[i][j] += dp[i][s]%MOD;
                                break;
                            }
                        }
                    }
                    if(dp[i-1][j] != -5) {
                        //위쪽에서 오는길이 직진이 아님
                        dp[i][j] += dp[i-1][j] %MOD;
                    }else {
                        //위쪽에서 오는길이 직진임
                        for(int s = i-2; s >= 1; s--) {
                            if(dp[s][j] != -5) {
                                dp[i][j] += dp[s][j]%MOD;
                                break;
                            }
                        }
                    }
                }
            }
        }
 
        return dp[m][n] % MOD;
        
    }

프로그래머스 테스트 케이스 통과

느낀 점: 나름 문제를 잘 이해하고 잘 풀었다고 생각한다. 하지만 시간이 조금 걸렸던 게 흠이었다. 이게 만약 실전에서 나왔다면 나는 많은 시간을 할애했을 것 같다. 물론 이제는 알았으니 조금은 줄일 수 있겠지만 말이다. 

 

**피드백은 언제나 환영입니다!