[프로그래머스][Java] Lv.3 등굣길

문제설명

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

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

 

제한사항

• 격자의 크기 m, n은 1이상 100이하인 자연수입니다. (m=n=1인 경우 X)
• 물에 잠긴 지역은 0개이상 10개 이하
• 집과 학교가 물에 잠긴 경우 X

---

풀이과정

1. 최단경로 개수를 저장하기 위한 cnt배열을 (m+1)*(n+1)사이즈로 만든다.
2. cnt 배열과 같은 크기의 puddle배열을 만들어 물에 잠긴 좌표를 저장한다.
   
   
3. for문을 사용하여 각 좌표를 방문한다.
4. 검사하는 좌표가 물이 잠긴 지역이라면 다음 검사를 위해 continue
5. 점화식은 cnt[i][j] = cnt[i-1][j]+cnt[i][j-1]이므로 왼쪽 좌표가 물에 잠기지 않았다면 경로 수를 더한다.
6. 위쪽 좌표 또한 물에 잠기지 않았다면 경로 수를 더해준다.
   
   
7. 5,6번 과정에서 최단경로의 개수가 너무 커지는 것을 막기 위해 1,000,000,007로 나눈 나머지를 더해준다.
8. 마지막 답을 도출할 때에도 1,000,000,007로 나눈 나머지값을 return해야 한다.

 

코드

class Solution {
    static int mod = 1000000007;
    static int[][] cnt; //최단거리 저장
    static boolean[][] puddle; //웅덩이 위치 저장
    public int solution(int m, int n, int[][] puddles) {
        
        cnt = new int[m+1][n+1];
        cnt[1][1]=1;
        puddle = new boolean[m+1][n+1];
        
        for(int i=0;i<puddles.length;i++){
            int[] temp = puddles[i];
            puddle[temp[0]][temp[1]]=true; //웅덩이 저장
        }
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(puddle[i][j]) continue; //물웅덩이가 있으면 검사 안함.
                
                if(!puddle[i-1][j]) cnt[i][j]+=cnt[i-1][j]%mod; //왼쪽에서 오는 경우
                if(!puddle[i][j-1]) cnt[i][j]+=cnt[i][j-1]%mod; //위쪽에서 오는 경우
            }
        }
        return cnt[m][n]%mod; //마지막 return할 때에도 %mod 해줘야 함.
    }
}

 

효율성 오류...

시행착오

 

정확성이 아닌 효율성에서 계속 반타작이 나서 다른 사람의 풀이를 참고하였는데 너무나 어이없는 실수였다.

마지막 return할 때 %mod를 해주지 않아 효율성 테스트에서 실패했던 것이었다....

---

다른 사람 풀이

 

굳이 puddles를 담는 boolean배열을 만들어 주지 않고,

최단경로 개수를 저장하는 배열에 -1값으로 웅덩이 표시를 해줄 수 있다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        int mod=1000000007;
        int[][] cnt = new int[m+1][n+1]; // 최단거리 개수 저장
        cnt[1][1]=1;//첫 시작 지점은 1로 시작.
        
        for(int i=0;i<puddles.length;i++){
            cnt[puddles[i][0]][puddles[i][1]]=-1; //굳이 boolean 배열 필요없이 -1로 표시.
        }
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //물웅덩이 지점은 검사하지 않음.
                if(cnt[i][j]==-1) continue;
                
                if(cnt[i-1][j]>0) cnt[i][j]+=cnt[i-1][j]%mod; //왼쪽에서 오는 경우
                if(cnt[i][j-1]>0) cnt[i][j]+=cnt[i][j-1]%mod; //위에서 오는 경우
            }
        }
        return cnt[m][n]%mod;
    }
}