문제

[프로그래머스] 보행자 천국
https://school.programmers.co.kr/learn/courses/30/lessons/1832

풀이

조건

• 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.
• city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.
  • 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
  • 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
  • 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다.
    • 왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 가능한 경로 수를 20170805로 나눈 나머지 값을 출력한다.

풀이 순서

• DP를 3차원 배열로 구현해서 해결합니다.
  • cityMap보다 행, 열 크기가 1 더 큰 배열이 2개 있다고 생각하면 됩니다.
  • 1 더 크게 만드는 이유: i + 1이나 j + 1 위치의 값을 구해 넣는 풀이를 사용하기 때문
• 위치의 상태(state)에 따라 구분합니다.
  • state == 0
    • 오른쪽, 아래쪽 모두 갈 수 있음
  • state == 2
    • 이전의 방향으로만 갈 수 있음
  • state == 1
    • 갈 수 없음

코드

Java

import java.util.*;

class Solution {
    int MOD = 20170805;  
    
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        
        // 가로로 가는 방향 : 1
        // 세로로 가는 방향 : 2
        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++) {
                int state = cityMap[i][j]; // 현재 위치의 상태
                // 오른쪽, 아래 둘 다 갈 수 있음
                if(state == 0) {
                    // 세로 -> 오른쪽, 아래 모두 이동 가능
                    dp[0][i + 1][j] += (dp[0][i + 1][j] + dp[0][i][j] + dp[1][i][j]) % MOD;
                    // 가로 -> 오른쪽, 아래 모두 이동 가능
                    dp[1][i][j + 1] += (dp[1][i][j + 1] + dp[1][i][j] + dp[0][i][j]) % MOD;
                } 
                // 이전의 방향으로만 갈 수 있음
                else if(state == 2) {
                    // 세로 -> 세로 방향으로만 이동 가능
                    dp[0][i + 1][j] = (dp[0][i + 1][j] + dp[0][i][j]) % MOD;
                    // 가로 -> 가로 방향으로만 이동 가능
                    dp[1][i][j + 1] = (dp[1][i][j + 1] + dp[1][i][j]) % MOD;
                }
            }
        }
        
        answer = (dp[0][m - 1][n - 1] + dp[1][m - 1][n - 1]) % MOD;
        
        return answer;
    }
    
}

정리

• 3차원 배열을 사용해 해결하는 방법을 배웠다.
• 처음에 상태가 2인 위치는 세지 않고 상태가 0인 위치까지 통과시키는 방법을 사용했는데 틀렸었다.