190122 DP (4) 등굣길

2019-01-22

DP (4) 등굣길

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항
  • 격자의 크기 M, N은 1 이상 100 이하인 자연수입니다.
  • 물에 잠긴 지역은 0개 이상 10개 이하입니다.
  • 집과 학교는 물에 잠기지 않았습니다.
입출력 예
m n puddles return
4 3 [[2, 2]] 4
풀이 과정
  • 처음엔 DFS 문제인줄 알고 열심히 DFS코드를 작성!
class Solution {
    static int[][] map= new int[101][101]; // 인덱스 1~100 사용
    static int[] dx={0,0,1,0,-1};
    static int[] dy={0,1,0,-1,0};
    static int M,N;
    static int route=0;
    public void dfs(int x,int y){
        if(x<=0||y<=0||x>N||y>M)
            return;
        if(map[x][y]==1 || map[x][y]== 5)
            return;
        if(map[x][y]==9)
            route++;
        for(int i=1;i<=4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(map[nx][ny]!=5) 
                dfs(ny,nx);
        }
    }
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        map[1][1]=9;
        map[m][n]=9;
        M=m;
        N=n;
        for(int i=0;i<puddles.length;i++){
            map[puddles[i][0]][puddles[i][1]]=1;
        }
        dfs(1,1);// 탐색 시작
        answer=route%1000000007;
        return answer;
    }
}
  • 하지만 DFS는 한 개의 경로만 찾을 수 있다!
  • 경로의 경우의 수를 찾는 법을 생각해보다가 초딩때(중딩때?) 사용하던 덧셈을 통해 얻는 방법을 생각해보았다.
class Solution {
    static int[][] map= new int[102][102];
    public int solution(int m, int n, int[][] puddles) {
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1 || j==1)
                    map[i][j]=1;
                else
                    break;
            }
        }
        for(int i=0;i<puddles.length;i++){
            map[puddles[i][1]][puddles[i][0]]=-1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1 && j==1)
                    continue;
                else if(map[i][j]==-1)
                    map[i][j]=0;
                else if(i==1)
                    map[i][j]=map[i][j-1];
                else if(j==1)
                    map[i][j]=map[i-1][j];
                else
                    map[i][j]=(map[i-1][j]+map[i][j-1])%1000000007;
            }
        }
        return map[n][m];
    }
}