[Lv.3] 등굣길 -자바

이 문제의 핵심은 "오른쪽과 아래쪽으로만"움직인다는 것이다

(이걸 안보고 처음 코드를 냈을 때 모든 테스트케이스를 틀려 많이 당황했었다..)

i,j점을 오는 최단 경로는 i-1,j점까지의 최단경로+i,j-1까지의 최단경로가 되는 것이다.

로직 자체는 쉬우니 dp만 알면 이해가 될거라 생각한다.

 

우선 첫행, 첫열을 모두 1로 초기화하고 장애물이 첫행이나 첫열에 놓이면 그 밑의 경우의수를 모두 0으로 바꾼 후

2행부터 그리고 2열부터 끝까지 검사하는 방식으로 코드를 짜 제출했더니, 3~4개의 테스트케이스에서 실패하게 됐다..

 

그러다, 질문게시판에서 그 이유를 찾게 되었다.

이런 코드라면 중간에 가는길이 막혔을 때 그 아래에 1로 초기화  된 값에 의해 최단 경로수가 0이 아닐 수 있다는 것이다.

사실, 장애물이 1행 혹은 1열에 들어오면 그 아래의 혹은 옆의 값을 모두 0으로 다시 바꿔 이런 문제를 해결했다고 생각했지만

 

내가 생각하지 못한 경우가 있을 수 있다고도 생각했고, 또, 훨씬 간단하게 풀 수 있는 방법이 있어 그걸 적용해봤다.

그냥, 1행 1열을 모두 초기화 시키는 것이 아니라, 1,1좌표의 값만 1로 초기화 한 후 별다른 과정 없이 dp값 갱신만 쭉 하면 끝이였다.

문제에서 오른쪽과 아래쪽으로만 움직인다고 했기에 1행부터 쭉 1열~n열까지 반복하며 자신의 왼쪽, 그리고 위쪽의 경우의수를 자신의 경우의수로 갱신하는 DP를 이용해 쭉 반복만 하게 되어도 앞서 고민했던 부분 모두 해결되는 것이다.

 

dfs,bfs 섞인 문제들 말고는 LV3에서 코드는 최대한 단순하게 만드는게 최고인 것같다..

 

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class Solution {
    public static final int DIV=1000000007;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp=new int[m+1][n+1];
//        for (int i = 0; i < m+1; i++) {
//            dp[i][1]=1;
//        }
//        for (int i = 0; i < n + 1; i++) {
//            dp[1][i]=1;
//        }
        dp[1][1]=1;
        Set<Puddle> puddleSet=new HashSet<>();
        for (int[] puddle : puddles) {
            puddleSet.add(new Puddle(puddle[0],puddle[1]));
            dp[puddle[0]][puddle[1]]=0;
//            if(puddle[0]==1){
//                for (int i = puddle[1]+1; i < m + 1; i++) {
//                    if(dp[1][i]==0)
//                        break;
//                    dp[1][i]=0;
//                }
//            }
//            if(puddle[1]==1){
//                for (int i = puddle[0]+1; i < m + 1; i++) {
//                    if(dp[i][1]==0)
//                        break;
//                    dp[i][1]=0;
//                }
//            }
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if(puddleSet.contains(new Puddle(i,j)))
                    continue;
                if(i==1&&j==1)
                    continue;
                dp[i][j]=(dp[i][j-1]+dp[i-1][j])%DIV;
//                System.out.println("i,j"+i+ " / "+j + "and val : "+dp[i][j]);
            }
        }
        return dp[m][n]%DIV;
    }
    class Puddle{
        int x,y;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Puddle puddle = (Puddle) o;

            if (x != puddle.x) return false;
            return y == puddle.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        public Puddle(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

추가로, 사용한 테스트케이스도 첨부합니다.

출처 : https://school.programmers.co.kr/questions/15698

System.out.println(sol.solution(2, 2, new int[][]{})+ " / " + 2);//2
System.out.println(sol.solution(3, 3, new int[][]{})+ " / "+ 6);  //6
System.out.println(sol.solution(3, 3, new int[][]{{2, 2}})+ " / " +2);//2
System.out.println(sol.solution(3, 3, new int[][]{{2, 3}})+ " / "+ 3);//3
System.out.println(sol.solution(3, 3, new int[][]{{1, 3}})+ " / "+5);//5
System.out.println(sol.solution(3, 3, new int[][]{{1, 3}, {3, 1}})+ " / "+4); //4
System.out.println(sol.solution(3, 3, new int[][]{{1, 3}, {3, 1}, {2, 3}})+ " / "+2); //2
System.out.println(sol.solution(3, 3, new int[][]{{1, 3}, {3, 1}, {2, 3}, {2, 1}}) + " / "+ 1);
System.out.println(sol.solution(7, 4, new int[][]{{2, 1}, {2, 2}, {2, 3}, {4, 2}, {4, 3}, {4, 4}, {6, 2}, {6, 3}})+ " / "+ 0); // 이 값이 잘 나오면 테스트1, 테스트9 통과, 위로 가면 안됨
System.out.println(sol.solution(4, 4, new int[][]{{3, 2}, {2, 4}})+ " / "+ 7);
System.out.println(sol.solution(100, 100, new int[][]{}) + " / "+ 690285631);