[프로그래머스] 등굣길 - Java

• 등굣길

풀이과정

• 주어진 n과 m에 대하여 이동 가능한 길을 grid로 나타낼 수 있다. 예를 들어 n = 3, m = 4이면 아래 그림과 같다.
  
• 문제의 제한 조건으로 이동 방향은 우측 및 하단 뿐이므로, 출발지점에서 우측과 하단으로 이동 가능한 방법의 수는 아래의 그림과 같이 나타낼 수 있다. 각각 오른쪽으로만 계속 이동하거나, 하단으로만 계속 이동해야 도달할 수 있는 위치이므로 이동가능한 방법의 가짓수는 모두 1이다.
  
• 나머지 비어있는 cell 들로 이동할 수 있는 방법은, 바로 위 cell에서 아래로 이동하거나 바로 왼쪽 cell에서 우측으로 이동하는 것 뿐이므로 나머지 각각의 cell들에 대한 이동 가능한 방법의 수는 바로 위쪽 cell까지 이동 가능한 방법의 수 + 바로 왼쪽 cell까지 이동 가능한 방법의 수이다. 이를 적용하면 다음과 같은 결과를 얻을 수 있다.
  
• 만일 중간에 물 웅덩이가 있다면, 물 웅덩이로는 이동할 수 없으므로 물 웅덩이가 있는 cell로의 이동 가능한 방법의 수는 0이다. 따라서 문제에 주어진 예제 1번의 경우 다음과 같은 grid가 그려진다.
  
• 또다른 예시로 물 웅덩이가 좌측 또는 상단 가장자리에 있을 경우를 생각 해 보면 다음과 같은 grid를 얻을 수 도 있다. (물 웅덩이가 (0,2), (1,0) cell에 존재할 경우)
  

Code

import java.util.Arrays;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        // true -> 이동 가능, false -> 물 웅덩이
        boolean[][] availableRoads = new boolean[n][m];
        for (boolean[] roads : availableRoads) {
            Arrays.fill(roads, true);
        }
        for (int[] puddle : puddles) {
            availableRoads[puddle[1] - 1][puddle[0] - 1] = false;
        }

        int[][] availableRouteCount = new int[n][m];

        // 위쪽 가장자리에서 오른쪽으로 이동
        for (int col = 1; col < m; col++) {
            if (!availableRoads[0][col]) {
                // 더이상 오른쪽으로 이동 불가능
                break;
            }
            availableRouteCount[0][col] = 1;
        }
        // 왼쪽 가장자리에서 아래쪽으로 이동
        for (int row = 1; row < n; row++) {
            if (!availableRoads[row][0]) {
                // 더이상 아래쪽으로 이동 불가능
                break;
            }
            availableRouteCount[row][0] = 1;
        }

        for (int row = 1; row < n; row++) {
            for (int col = 1; col < m; col++) {
                availableRouteCount[row][col] = availableRoads[row][col] ? (availableRouteCount[row - 1][col] + availableRouteCount[row][col - 1]) % 1_000_000_007 : 0;
            }
        }

        return availableRouteCount[n - 1][m - 1];
    }
}

결과