[프로그래머스] 등굣길

링크

[프로그래머스]등굣길

문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  ** m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m n puddles return
4 3 [[2, 2]] 4

입출력 예 설명

과정

1. 0,0을 1,1로 시작하기 때문에 물웅덩이의 좌표를 1씩 감소
2. 오른쪽 또는 아래로 이동하여 모든 경로 합 계산(메모이제이션 적용 필수)
3. 기저사례는
   1. 보드 범위 벗어남
   2. 집 도착
   *3. 물웅덩이 밟음

정확성, 효율성 테스트가 있는 문제였다.
메모이제이션을 적용하면 간단하게 통과할 수 있었다!

코드

class Solution {
    int[][] memo;
    int[][] mBoard;
    int NA = 1000000007;
    public int solution(int x, int y, int[][] puddles) {
        int board[][] = new int[y][x];
        memo = new int[y][x];
        
        for(int[] puddle : puddles){
            board[puddle[1]-1][puddle[0]-1] = -1;
        }
        for(int i= 0; i<y; i++)
            for(int j=0; j<x ; j++)
                memo[i][j] = -1;
        mBoard = board;
        
        int answer = gogo(0,0);
        
        return answer;
    }
    
    private int gogo(int y, int x){
        //기저사례
        if(y >= mBoard.length || x >= mBoard[0].length) return 0; //범위
        if(mBoard[y][x] == -1) return 0; //웅덩쓰
        if(y == mBoard.length-1 && x == mBoard[0].length-1) return 1; //도착
        
        //메모이제이션
        if(memo[y][x] != -1) return memo[y][x];
        
        //탐색
        return memo[y][x] = (gogo(y+1,x)%NA + gogo(y,x+1)%NA)%NA;
        
    }
}