[Programmers] 등굣길 - Java

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

프로그래머스

---

1. 문제

mxn 크기 map에서 물웅덩이를 제외한 좌표를 지나 1,1에서 m,n까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 구한다.

 

2. 풀이

완전탐색으로 접근해서 풀었는데 실패+시간초과가 나온다.

dp로 풀어야할 듯 하다. 다익스트라처럼 풀어보자.

 

 

3. 코드

완탐 실패 코드

class Solution {
    
    static long min = Integer.MAX_VALUE;
    static int M, N, map[][];
    static int[] dy={0,1};
    static int[] dx={1,0};
    
    public int solution(int m, int n, int[][] puddles) {
        M = m;
        N = n;
        map = new int[m+1][n+1];
        for (int[] loc: puddles) {
            map[loc[0]][loc[1]] = 1;
        }
        dfs(1,1,0);
        
        return (int) (min%1000000007);
    }
    
    static void dfs(int y, int x, int cnt) {
        if (cnt > min) return;
        if (y==M && x==N) {
            if (cnt-1 < min) min = cnt-1;
            return;
        }
        
        for (int d=0; d<2; d++) {
            int ny = y+dy[d];
            int nx = x+dx[d];
            if (ny<=0 || ny>M || nx<=0 || nx>N || map[ny][nx] == 1) continue;
            dfs(ny, nx, cnt+1);
        }
    }
}

 

 

4. 사담

[23/8/4]

완탐으로 풀었는데 실패 + 시간초과가 나왔다. dp처럼 좌표에 올 수 있는 최솟값을 저장하고 비교하는 방식이 효율적인걸까? 그렇게 풀어봐야겠다.