[programmers] 등굣길

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

코딩테스트 연습 - 등굣길

 

 

수학 문제로 자주 나오던 경로의 수 문제 ..?? 랑 똑같다고 생각해서 고거대로 풀음(예외 제외)

 

 

 

 

조금 신경써서 고려했던 점

- puddles=0 인 경우

- 나머지 개수를 return해야 함

- puddle 위치에 따라 갈 수 없는 위치가 추가적으로 생김 (*)

 

 

+

이동방향이 오른쪽, 아래 두 가지이며

목적지가 오른쪽 하단에 존재하기 때문에 단순한 dfs 적용으로도 해결 가능 

 

 

import java.util.Arrays;

class Solution {
    public static int solution(int m, int n, int[][] puddles) {
        int answer = 0;

        int[][] streets = new int[n+1][m+1];
        for (int i = 0; i < streets.length; i++) {
            Arrays.fill(streets[i], -1);
        }

        //puddles
        int a, b;
        for (int i = 0; i < puddles.length; i++) {
            if (puddles[i].length == 2) {	//puddle 개수 체크
                a = puddles[i][0];
                b = puddles[i][1];
                streets[b][a] = 0;
            }
        }

        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) {
                if (streets[row][col] == 0) continue;
                if (col == 1 && row == 1) {
                    streets[row][col] = 1;
                    continue;
                }

                if (col == 1 || row == 1) {
                //(*)
                    if (row == 1) {
                        streets[row][col] = streets[row][col - 1];
                    } else if (col == 1) {
                        streets[row][col] = streets[row - 1][col];
                    }
                } else {
                    streets[row][col] = (streets[row][col - 1] + streets[row - 1][col]) % 1000000007;
                }
            }
        }
        answer = streets[n][m];
        return answer;
    }
}