[프로그래머스/Lv. 3] 등굣길 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int mod = 1_000_000_007;
    
    public int solution(int m, int n, int[][] puddles) {
        
        int[][] dp = new int[n + 1][m + 1];
        
        // dp 배열 초기화
        dp[1][1] = 1;
        for(int[] puddle : puddles) dp[puddle[1]][puddle[0]] = -1;
        
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= m ; j++) {
                if(dp[i][j] == -1)   continue;   // 웅덩이라면 패스
                
                if(dp[i - 1][j] > 0)  dp[i][j] += dp[i - 1][j] % mod;    // 위쪽 값
                if(dp[i][j - 1] > 0)  dp[i][j] += dp[i][j - 1] % mod;    // 왼쪽 값
            }
        }
        
        return dp[n][m] % mod;
    }
}
 

 

 

🧩 해결 아이디어

• DP

- dp 배열 초기화 값 : 출발 지점은 1, 장애물은 -1로 설정

 

- dp 배열 완전탐색하면서 해당 칸 값이 -1이라면 웅더이이므로 패스

- 위쪽 값이 0보다 크다면, 현재 값에 위쪽 값을 더함

- 왼쪽 값이 0보다 크다면, 현재 값에 왼쪽 값을 더함

 

 

💥 유의사항

- else if로 하면 왼쪽과 위쪽값을 모두 포함시킬 수 없으므로 두 경우를 모두 처리하도록 if문 사용

- 12번째 줄에서dp[ puddle[1] ][ puddle[0] ] = -1;이 아닌 dp[ puddle[1] ][ puddle[0] ] = -1;이어야 함

 

 

 

---

💬 느낀 점

최단 경로래서 BFS로 풀 수는 있는데 효율성에서 통과가 안 된당

 

효율성 해결 방법 중에는 이런 것도 있었다.

프로그래머스

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 등굣길 JAVA