[Java] Lv.3 등굣길

문제

 

프로그래머스

 

문제 풀이

어떻게 풀어야할지 감이 안와서 아래의 글을 참고 했다.

map의 가장 윗 줄과 가장 왼쪽 줄은 최단 거리가 1개 밖에 없다는 점을 이용하여 다 1로 채우고 (물 웅덩이가 있는 경우는 제외)

특정 칸의 최단 거리 개수를 구할 때 윗 칸과 왼쪽 칸의 값을 확인하여 더해서 기록한다는 발상을 활용한다.

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

 

자바 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        // 해당 위치로 가기위한 최단 경로 수를 기록할 배열
        int[][] map = new int[n][m];
        
        // 물 웅덩이 위치 값 -1
        if(puddles[0].length > 0){
            for(int[] p : puddles){
                map[p[1] - 1][p[0] - 1] = -1;
            }
        }
        
        // 가로 맨 윗 줄 최단 경로 수 기록
        for(int i = 1; i < n; i++){
            // 맨 윗줄은 최단 경로로 가는 방법이 무조건 1개 밖에 없다.
            // 다만 이전 칸의 맵이 웅덩이가 있을 경우 해당 칸에 도달할 수 없다.
            map[i][0] = (map[i][0] == -1 | map[i - 1][0] == -1) ? -1 : 1; 
        }
        for(int i = 1; i < m; i++){
            // 맨 윗줄은 최단 경로로 가는 방법이 무조건 1개 밖에 없다.
            // 다만 이전 칸의 맵이 웅덩이가 있을 경우 해당 칸에 도달할 수 없다.
            map[0][i] = (map[0][i] == -1 | map[0][i - 1] == -1) ? -1 : 1; 
        }
        
        // 각 칸 마다 최단 경로 수를 확인하기 위해
        // 한 칸 씩 위와 왼쪽 칸을 확인하여 최단 경로 수를 더 해준다.
        for(int i = 1; i < n; i++)
            for(int j = 1; j < m; j++){
                // 해당 위치가 물웅덩이가 아닐 경우 위와 왼쪽 칸을 확인해서 경로 수를 더해준다.
                if(map[i][j] != -1){
                    int top = map[i - 1][j] == -1 ? 0 : map[i - 1][j];
                    int left = map[i][j - 1] == -1 ? 0 : map[i][j - 1];
                    map[i][j] = top + left == 0 ? -1 : (top + left) % 1000000007;
                }
            }
        
        // 도착점의 위와 왼쪽 칸이 둘 다 물웅덩이라서 도달할 수 없는 경우 0
        // 이외에는 배열에 저장된 값을 출력한다.
        return map[n - 1][m - 1] == -1 ? 0 : map[n - 1][m - 1];
    }
}