Programmers - 보행자 천국 with JAVA

 

 

 

로직 (DP)

기본적인 로직은 다음과 같다.

1. 위와 왼쪽 블록을 값을 확인해 조건에 맞게 더해준다.

2. 위 또는 왼쪽 블록이 막혀있다면 0을 더해준다. 만약 회전 불가 칸이라면 위쪽을 조사하고 있다면 그 바로 위의 값을 다시 확인, 왼쪽도 마찬가지로 그 왼쪽 칸을 다시 확인한다.

3. 결과 도출

 

 

오류가 발생했었다.

기존의 코드 -> 주어진 Map의 1과 2를 -1과 -2로 바꾸고 주어진 해당 Map에 DP 적용

변경 코드 -> 새로운 Map을 생성해 동일 로직 처리

 

오류가 발생한 원인은 찾지 못했다. 일단은 앞으로 새로운 맵을 만들어서 사용하는 것이 맞을 것 같다.

 

 

 

코드

- 틀린 코드

class Solution {
    public static int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        for(int x=0; x<m; x++){
            for(int y=0; y<n; y++){
                if(cityMap[x][y] == 1){
                    cityMap[x][y] = -1;
                }
                if(cityMap[x][y] == 2){
                    cityMap[x][y] = -2;
                }
            }
        }
        for(int x=0; x<m; x++){
            for(int y=0; y<n; y++){
                if(x == 0 && y == 0){
                    cityMap[0][0] = 1;
                    continue;
                }
                if(cityMap[x][y] == 0){
                    cityMap[x][y]=(Up(x,y,cityMap)+Left(x,y,cityMap))%MOD;   
                }
            }
        }
        return cityMap[m-1][n-1];
    }
    public static int Up(int x, int y, int[][] cityMap){
        if(x-1 < 0){
            return 0;
        }
        if(cityMap[x-1][y] == -1){
            return 0;
        }
        if(cityMap[x-1][y] == -2){
            return Up(x-1, y, cityMap);
        }
        return cityMap[x-1][y];
    }
    public static int Left(int x, int y, int[][] cityMap){
        if(y-1 < 0){
            return 0;
        }
        if(cityMap[x][y-1] == -1){
            return 0;
        }
        if(cityMap[x][y-1] == -2){
            return Left(x, y-1, cityMap);
        }
        return cityMap[x][y-1];
    }
}

 

 

- 수정 코드

class Solution {
    public static int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int[][] map = new int[m][n];
        for(int x=0; x<m; x++){
            for(int y=0; y<n; y++){
                if(x == 0 && y == 0){
                    map[0][0] = 1;
                    continue;
                }
                if(cityMap[x][y] == 0){
                    map[x][y]=(Up(x,y,cityMap,map)+Left(x,y,cityMap,map))%MOD;   
                }   
            }
        }
        return map[m-1][n-1];
    }
    public static int Up(int x, int y, int[][] cityMap, int[][] map){
        if(x-1 < 0){
            return 0;
        }
        if(cityMap[x-1][y] == 1){
            return 0;
        }
        if(cityMap[x-1][y] == 2){
            return Up(x-1, y, cityMap, map);
        }
        return map[x-1][y];
    }
    public static int Left(int x, int y, int[][] cityMap, int[][] map){
        if(y-1 < 0){
            return 0;
        }
        if(cityMap[x][y-1] == 1){
            return 0;
        }
        if(cityMap[x][y-1] == 2){
            return Left(x, y-1, cityMap, map);
        }
        return map[x][y-1];
    }
}