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

프로그래머스 - 등굣길

class Solution {
    public int solution(int m, int n, int[][] puddles) {
       int[][] maps = new int[n+1][m+1];
        maps[1][1] = 1;
        
        for(int[] puddle : puddles) {
            // (m, n)으로 위치 표기 -> [1]이 y, [0]이 x
            maps[puddle[1]][puddle[0]] = -1;
        }
        
        for(int i = 1; i<= n; i++) {
            for(int j=1; j<=m; j++) {
                if( i == 1 && j == 1) continue;
                
                // 웅덩이에서 우측으로 가도 갈 수 없으니 경우의 수 0으로 처리하기 위함
                    if(maps[i][j] == -1) {
                        maps[i][j] = 0;    
                        continue;
                    }
                if(i-1 >0) {
                    // 위 & 좌측 모두에서 올 수 있는 칸인 경우
                    if(j-1 > 0) {
                        maps[i][j] = (maps[i-1][j] % 1_000_000_007) + (maps[i][j-1] % 1_000_000_007);
                    }
                    // 위측에서만 올 수 있는 칸이라면
                    else {
                        maps[i][j] = (maps[i-1][j] % 1_000_000_007);
                    }
                }
                // 좌측에서만 올 수 있는 칸인 경우
                 else if(j-1 >0) {
                        maps[i][j] = (maps[i][j-1] % 1_000_000_007);
                }
            }
        }
        return maps[n][m] % 1_000_000_007 ;     
    }
}

• 유튜브 영상을 먼저 보시고 해당 내용 보시면 이해가 더 잘 될것입니다.

• 블로그 설명만 보곤 잘 이해가 되지 않아서 영상보고 제가 코드를 조금 변형하였습니다.

• 풀이법

  • 특정 칸으로 오는 최단 경로는 해당칸 위에서 오거나 좌측에서 오는 경우 뿐이 없음(아래 유튜브 영상 참조)

    • 우측 또는 아래쪽으로만 이동 가능하기에
      | - | 1 | - | - |
      | 1 | ㅇ(2) | - | - |
    • ㅇ 위치에서는 위에서 오는 경우 + 왼쪽에서 오는 경우

  • 따라서 위나 왼쪽이 유효한 경로인지 확인, 만일 현재 위치가 웅덩이라면 0으로 세팅 -> 위나 왼쪽 값 더해줄 때 웅덩이면 0 더해서 없는셈 치도록

  • 전부 다 더한 후 숫자로 나누면 큰 수를 나누기에 효율성에서 떨어짐. 매번 다 나눈 값을 저장하고 마지막에 한번 더 나눠준다.

  • 자바에서 _는 천단위 구분 기호로 사용 가능

• 출처

  • [JAVA/프로그래머스] 동적계획법(Dynamic Programming)_등굣길
  • 경우의 수 최단경로문제 쉽게 이해하기