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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 메모제이션을 통해 출발 지점인 (0, 0) 부터 도착 지점인 (m - 1, n - 1) 까지 도달할 수 있는 경로를 구하도록 했습니다. DFS를 이용하여 도달할 수 있는 경로를 일일이 카운팅하는 법도 있겠지만 m과 n이 최대 500까지 되므로 시간 초과 이슈로 인해 적용하기엔 다소 어렵습니다.

 

우선 파라미터로 입력받는 지도 데이터인 cityMap과 별도로 메모제이션을 위한 sum 배열을 선언해주었습니다. 이때 배열을 다음과 같이 3차원 배열로 선언해주었는데, 이에 대해선 좀 더 아래에서 자세히 다루고자 합니다.

 

    int[][][] sum = new int[m][n][3]; // 0일 경우 : 0, 2일 경우 오른쪽 : 1, 2일 경우 아래 : 2

 

메모제이션을 하기 앞서 0번째 행과 0번째 열의 경우 벽(원소값 : 1)을 만나기 직전까지 일직선상 이동할 수 있으므로 다음과 같이 1로 초기화 시켜주었습니다. 이동 방향이 오른쪽이나 아래쪽으로 한정되어있으므로 벽 이후에 경로는 존재할 수 없기 때문입니다. 다만, 원소값이 2인 지점이어도 직진은 가능합니다. (좌회전과 우회전은 불가능)

 

        for (int i = 1; i < n; i++) {
            if (cityMap[0][i] != 1) {
                sum[0][i][0] = 1;
            } else {
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            if (cityMap[i][0] != 1) {
                sum[i][0][0] = 1;
            } else {
                break;
            }
        }

 

이제 (1, 1) 지점을 시작으로 마지막 (m - 1, n - 1) 지점까지 2차원 배열을 순회해주면서 왼쪽 값과 위쪽 값을 기준으로 경로 개수를 메모제이션 해줍니다. 이때 왼쪽 및 위쪽 값들이 기준이 되는 이유는 앞서 언급했듯이 이동 방향이 아래 또는 오른쪽 방향만 가능하기 때문입니다.

 

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                sum[i][j][0] = (sum[i][j][0] + sum[i - 1][j][0]) % MOD;
                sum[i][j][0] = (sum[i][j][0] + sum[i][j - 1][0]) % MOD;
            }
        }

 

하지만, 현재 순회 지점의 값이 벽(원소값 : 1)일 경우에는 경로가 존재할 수 없으므로 메모제이션을 해선 안되며, 왼쪽 및 위쪽 지점이 빈 지점(원소값 : 0)일 경우인지 직진만 가능한 지점(원소값 : 2)일 경우인지에 따라 다른 방식으로 메모제이션 해줄 필요가 있습니다.

 

먼저 현재 순회 지점이 빈 지점인데다가 왼쪽 값과 위쪽 값까지 모두 빈지점이라면 단순히 경로를 더해주면 됩니다. 하지만 이때 왼쪽 값과 위쪽 값이 직진만 가능한 지점이라면 아래와 같이 나눠서 더해주어야 합니다.

 

앞서 sum 배열을 3차원으로 나눈 이유는 이 때문인데, 빈 지점에서 왔는지와 직진만 가능한 지점에서 위에서 아래로 내려왔는지 또는 왼쪽에서 오른쪽으로 지나왔는지를 구분해서 저장하기 위함입니다. 이번엔 현재 순회 지점이 직진만 가능한 지점일 경우에는, 왼쪽에서 왔는지 위쪽에서 왔는지와 그 지점이 빈 지점인지 직진만 가능한 지점인지를 동시에 구분하여 메모제이션해줍니다.

 

아래 그림과 위 그림은 현재 지점의 상태를 제외하면 사실상 동일합니다.

 

최종적으로 메모제이션 시 MOD 값(20170805)으로 나머지 연산을 해주면서(모듈러 연산) 마지막으로 메모제이션된 도착 지점 (m - 1, n - 1)의 값을 반환해줍니다.

 

나의 소스 코드

class Solution {

    final int MOD = 20170805;

    public int solution(int m, int n, int[][] cityMap) {
        int[][][] sum = new int[m][n][3]; // 0일 경우 : 0, 2일 경우 오른쪽 : 1, 2일 경우 아래 : 2
        for (int i = 1; i < n; i++) {
            if (cityMap[0][i] != 1) {
                sum[0][i][0] = 1;
            } else {
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            if (cityMap[i][0] != 1) {
                sum[i][0][0] = 1;
            } else {
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (cityMap[i][j] == 0) {
                    if (cityMap[i - 1][j] == 0) {
                        sum[i][j][0] = (sum[i][j][0] + sum[i - 1][j][0]) % MOD;
                    } else if (cityMap[i - 1][j] == 2) {
                        sum[i][j][0] = (sum[i][j][0] + sum[i - 1][j][2]) % MOD;
                    }

                    if (cityMap[i][j - 1] == 0) {
                        sum[i][j][0] = (sum[i][j][0] + sum[i][j - 1][0]) % MOD;
                    } else if (cityMap[i][j - 1] == 2) {
                        sum[i][j][0] = (sum[i][j][0] + sum[i][j - 1][1]) % MOD;
                    }
                } else if (cityMap[i][j] == 2) {
                    if (cityMap[i - 1][j] == 0) {
                        sum[i][j][2] = (sum[i][j][2] + sum[i - 1][j][0]) % MOD;
                    } else if (cityMap[i - 1][j] == 2) {
                        sum[i][j][2] = (sum[i][j][2] + sum[i - 1][j][2]) % MOD;
                    }

                    if (cityMap[i][j - 1] == 0) {
                        sum[i][j][1] = (sum[i][j][1] + sum[i][j - 1][0]) % MOD;
                    } else if (cityMap[i][j - 1] == 2) {
                        sum[i][j][1] = (sum[i][j][1] + sum[i][j - 1][1]) % MOD;
                    }
                }
            }
        }

        return sum[m - 1][n - 1][0];
    }
}

 

참고자료

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