프로그래머스 Lv.3) 등굣길 (DP)

등굣길

코딩테스트 연습 - 등굣길

풀이

 

전에 풀었던 방법과 오늘 푼 방법이 같다.

다만, 차이점이 있다면 처음에는 map을 생성하고, 모든 길을 1로 적어뒀다.

그런 뒤에, 입력받은 웅덩이 위치를 0으로 표시하고, 웅덩이에 막힌 길을 0으로 표시했다.

맵이 완성되면 맵을 돌면서 갈 수 있는 방법을 더해가며 답을 구했다.

 

오늘 푼 풀이도 위와 같다고 보면 된다.

처음부터 dp 배열을 생성하고, 웅덩이만 -1로 표현해줬다.

그리고 dp를 돌면서 위와 왼쪽 길이 웅덩이인지 아닌지만 판단하여, 웅덩이가 아닌 경우에만 더하도록 해주었다.

추가적으로 웅덩이에서는 길찾기를 하지 않아 웅덩이가 사라지지 않도록 설정해주었다.

 

 

코드 1

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n+1][m+1];
        for(int y=1; y<=n; y++) {   // map 생성
            for(int x=1; x<=m; x++) {
                map[y][x] =1;
            }
        }
        for(int[] pos : puddles) {  // 웅덩이는 0으로 변환
            map[pos[1]][pos[0]] = 0;
        }
        
        map[0][1] =1;
        for(int y=1; y<=n; y++) {   // map 생성
            for(int x=1; x<=m; x++) {
                if(map[y-1][x] ==0 && map[y][x-1] ==0) {
                    map[y][x] =0;
                }
            }
        }

        return getResult(m,n, map);
    }
    private static int getResult(int m, int n, int[][] map) {
        for(int y=2; y<=n; y++) {
            for(int x=2; x<=m; x++) {
                if(map[y][x] !=0) {
                    map[y][x] = (map[y-1][x] + map[y][x-1]) % 1000000007;
                }
            }
        }
        
        return map[n][m];
    }
}

 

코드 2

 

class Solution {
    int[] dx = {-1,0};
    int[] dy = {0,-1};
    
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        final int MOD = 1000000007;
        for(int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] =-1;
        }
        dp[0][1] =1;
        for(int y=1; y<=n; y++) {
            for(int x=1; x<=m; x++) {
                if(dp[y][x] != -1) {
                    for(int i=0; i<2; i++) {
                        int ny = y+dy[i];
                        int nx = x+dx[i];
                        if(dp[ny][nx] != -1) {
                            dp[y][x] = (dp[y][x] + dp[ny][nx])%MOD;
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }
}