[프로그래머스] 등굣길 / JAVA

> 문제 설명 보기

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

코딩테스트 연습 - 등굣길

 

>IDEA

중고등학교적 많이 풀던 가장 짧은 거리의 개수를 구하는 문제다.

기본적으로 이전 도달 지점까지의 도달 개수를 다음 지점에서 더해주면 된다.

해당 방법을 기본으로 예외처리 (웅덩이)를 해주며 해결했다.

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        boolean[][] isPud = new boolean[m][n];
        long[][] map = new long[m][n];


        // Initialize
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                map[i][j] = 0;
            }
        }

        for(int[] intArr : puddles){
            isPud[intArr[0] - 1][intArr[1] - 1] = true;
        }

        map[0][0] = 1;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isPud[i][j]) continue;
                if(j > 0 && i > 0) {
                    if (isPud[i - 1][j] && isPud[i][j - 1]) {
                        isPud[i][j] = true;
                        continue;
                    }
                }
                if(j > 0){
                    if(!isPud[i][j-1]){
                        map[i][j] = (map[i][j] + map[i][j-1]) % 1000000007;
                    }
                }
                if(i > 0){
                    if(!isPud[i-1][j]){
                        map[i][j] = (map[i][j] + map[i-1][j]) % 1000000007;
                    }
                }
            }
        }

        return (int)(map[m-1][n-1]);
    }
}