Lv 3. 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=java

프로그래머스

 

// 완탐
// 상하좌우 Direction[]
// 방문체크를 어떻게 할것인가?주된 고민 사항
// while 문에서 매번 체크 (끝난건지? 몇개인지)
// import java.util.*;

// class Solution {
//     class Node{
//         int x;
//         int y;
//         int distance;
//         public Node(int x, int y, int distance){
//             this.x = x;
//             this.y = y;
//             this.distance = distance;
//         }
//     }
//     private Queue<Node> q = new ArrayDeque<>();
//     private int[][] isVisited;
//     private boolean[][] map;
//     private int[][] d = {{1,0},{0,1}};
//     private boolean find = false;
//     private int endDistance = Integer.MAX_VALUE;
    
//     private int bfs(int n,int m){
//         System.out.println("bfs method Start");
//         int answer = 0;
//         q.add(new Node(0,0,0));
//         while(!q.isEmpty()){
//             Node now = q.poll();
//             // System.out.println("now x = "+now.x+" && now y = " + now.y + " && now.dis = "+ now.distance);
//             // System.out.println("=======");
//             if(find && now.distance > endDistance) //찾았는데 만약 거리가 더크면
//                 break;
//             else if(now.x == n && now.y == m){ //찾았는데 첫답 또는 여러가지 답이면
//                 find = true;
//                 endDistance = now.distance;
//                 answer++;
//             }
//             for(int i = 0 ; i < 2 ; i++){
//                 int dx = now.x+d[i][0];
//                 int dy = now.y+d[i][1];
//                 if(dx > n || dy > m) //null 방지
//                     continue;
//                 if(isVisited[dx][dy] >= (now.distance+1) && !map[dx][dy]){ //가야할 지역이 가본적 없거나 이미가본곳이라도 거리가 같거나 물에잠기지 않았을때만
//                     // System.out.println("dx = "+dx+" dy = "+dy);
//                     q.add(new Node(dx,dy,now.distance+1));
//                     isVisited[dx][dy] = now.distance+1;
//                 }
//             }
//             // System.out.println("=======");
//         }
//         return answer;
//     }
//     public int solution(int m, int n, int[][] puddles) {
//         // System.out.println("solution method Start");
//         isVisited = new int[n][m];
//         map = new boolean[n][m];
        
//         //거리 초기화
//         for(int i = 0 ; i < n ; i ++){
//             for(int j = 0 ; j < m ; j++){
//                 isVisited[i][j] = Integer.MAX_VALUE;
//             }
//         }
        
//         for(int[] puddle : puddles)
//             map[puddle[0]-1][puddle[1]-1] = true;
//         return bfs(n-1,m-1);
//     }
// }

// 위는 시간초과 
// 이번엔 동적 계획법 DP로 푼다.
// DP를 통해 갈 수 있는 방법을 모두 +1 한다.

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        long[][] dp = new long[n][m];
        boolean[][] isPuddle = new boolean[n][m];
        // 물 웅덩이 위치 표시
        for (int[] puddle : puddles) {
            isPuddle[puddle[1] - 1][puddle[0] - 1] = true;  // y, x 순서로 저장
        }
        // 시작 지점이 물에 잠기지 않은 경우에만 1로 초기화
        dp[0][0] = isPuddle[0][0] ? 0 : 1;
        // 첫 번째 열 초기화
        for (int i = 1; i < n; i++) {
            if (isPuddle[i][0]) break;  // 물에 잠긴 곳은 이후 경로도 모두 0
            dp[i][0] = 1;
        }
        // 첫 번째 행 초기화
        for (int j = 1; j < m; j++) {
            if (isPuddle[0][j]) break;  // 물에 잠긴 곳은 이후 경로도 모두 0
            dp[0][j] = 1;
        }
        // DP 테이블 채우기
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (isPuddle[i][j]) {
                    dp[i][j] = 0;  // 물에 잠긴 곳은 경로가 없다
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
                }
            }
        }
        return (int) dp[n - 1][m - 1];
    }
}