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

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

class Solution {
    private static final int MOD = 1000000007;
    
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n][m];
        
        map[0][0] = 1;
        for (int[] puddle : puddles) map[puddle[1] - 1][puddle[0] - 1] = -1;
        
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (map[y][x] == -1) continue;
                if (0 <= x - 1 && map[y][x - 1] != -1) map[y][x] += map[y][x - 1] % MOD;
                if (0 <= y - 1 && map[y - 1][x] != -1) map[y][x] += map[y - 1][x] % MOD;
            }
        }
        return map[n - 1][m - 1] % MOD;
    }
}

 

---

 

후기

처음에 BFS로 접근했더니 시간 초과가 발생했다. 왜 그런가 생각해 봤는데 같은 곳을 두 번씩 계속 접근하기 때문에 이것이 문제가 되어 시간이 초과되었던 것 같다. 시간 초과라는 것은 더 나은 방법이 있다는 것...

좀 생각해 보니까 어차피 진행 방향은 아래 아니면 우측이기 때문에 2중 반복문을 돌려서 좌->우, 위->아래(실제로는 y값 증가지만 뒤집혔다고 생각했을 때)로 해결할 수 있을 것 같아 이렇게 해봤는데 통과했다.