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

문제

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

등굣길

풀이

집에서 학교 까지의 최단 경로의 수를 구하는 문제이다. 

아래, 우측 방향으로만 이동할 수 있고 물웅덩이는 지나갈 수 없다. 

행렬 크기 값이 보통 문제와 달리 반대로 주어지니, 헷갈리지 않도록 유의해야 한다.

처음에 dfs, bfs 로 시도했지만 정답은 맞지만 효율성에서 통과가 안된다.

해당 문제는 동적 계획법 카테고리에 있는 문제로, DP로 풀면 쉽게 해결할 수 있다. 

 

해당 칸까지 가는 최단 경로의 수

• 첫 번째 행에 있는 칸들은, 최단 경로의 수가 각각 1이다. 어떤 칸이든 좌측에서 진입한다.
• 첫 번째 행 칸의 최단경로 수 : map[i][j] = map[i][j-1]
• 첫 번쨰 열에 있는 칸들 또한 최단 경로의 수가 각각 1이다. 어떤 칸이든 위쪽에서 진입한다.
• 첫 번째 열 칸의 최단경로 수 : map[i][j] = map[i-1][j]
• 나머지 칸은 위에서 내려오는 경로의 수 + 좌측에서 들어오는 경로의 수를 더한 값이 최단 경로의 수가 된다. 
• map[i][j] = (map[i-1][j] + map[i][j-1])
• 단, puddle은 지나갈 수 없기 때문에 0으로 설정한다.

1 HOME	1	1	1
1	0 WATER	1	2
1	1	2	4 SCHOOL

소스코드

import java.util.*;

class Solution {

    public int answer, m, n;
    public int[][] map;
    public boolean[][] water;
    public int[][] dir = new int[][]{{1, 0}, {0, 1}};
    public int solution(int m, int n, int[][] puddles) {
        this.m = m;
        this.n = n;
        this.map = new int[n+1][m+1];
        this.water = new boolean[n+1][m+1];
        
        for(int i = 0; i < puddles.length; i++){
            water[puddles[i][1]][puddles[i][0]] = true;
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(water[i][j]){
                    map[i][j] = 0;
                    continue;
                }
                if(i == 1){
                    // 첫번째 행 처리 
                    if(j == 1) {
                        map[i][j] = 1; 
                    } else {
                        map[i][j] = map[i][j-1]%1000000007;
                    }   
                } else if(j == 1){
                    // 첫번째 열 처리
                    map[i][j] = map[i-1][j]%1000000007;
                } else {
                    // 나머지 행 처리
                    map[i][j] = (map[i-1][j] + map[i][j-1])%1000000007;
                }
                
            }
        }

        return map[n][m];
    }
      
    public boolean isValid(int x, int y){
        if(x <= 0 || y <= 0 || x > n || y > m || map[x][y] == -1) return false;
        return true;
    }
  
    
}