[프로그래머스] 등굣길

코드 힌트

1. 웅덩이 처리:
   • 웅덩이(puddles)로 지정된 셀은 경로 계산에서 제외됩니다.
   • 이 셀들은 -1로 표시하여, 이후 경로 계산에서 무시하도록 처리합니다.
2. 초기화:
   • 첫 번째 행과 첫 번째 열의 값을 초기화합니다.
   • 만약 웅덩이로 인해 막혀있는 경우 해당 경로는 막히며, 그렇지 않은 경우 1로 설정합니다.
   • 이는 초기 경로 설정을 위한 작업입니다.
3. 동적 프로그래밍:
   • 나머지 셀들은 동적 프로그래밍을 이용하여 계산합니다.
   • 각 셀의 경로 수는 왼쪽과 위쪽에서 올 수 있는 경로의 수를 합산하여 계산합니다.
   • 이 과정에서 현재 셀이 웅덩이인지 확인하고, 웅덩이가 아닌 경우에만 경로 수를 누적합니다.
4. 결과 반환:
   • 최종적으로 도착 지점 (m-1, n-1)의 셀에 저장된 경로 수를 반환합니다.
   • 결과는 매우 큰 수를 다룰 수 있으므로, 1,000,000,007로 나머지 연산을 수행하여 반환합니다.

 

---

정답은 더보기 클릭

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[m][n];
        
        // 웅덩이 초기화: 웅덩이는 -1로 표시
        for (int[] puddle : puddles) {
            map[puddle[0]-1][puddle[1]-1] = -1;
        }
        
        // 첫 번째 열 초기화: 웅덩이로 막혀 있지 않은 경우만 1로 설정
        for (int i = 1; i < m; i++) {
            if (map[i][0] != -1 && map[i-1][0] != -1) {
                map[i][0] = 1;
            } else {
                map[i][0] = -1;
            }
        }
        
        // 첫 번째 행 초기화: 웅덩이로 막혀 있지 않은 경우만 1로 설정
        for (int j = 1; j < n; j++) {
            if (map[0][j] != -1 && map[0][j-1] != -1) {
                map[0][j] = 1;
            } else {
                map[0][j] = -1;
            }
        }
        
        // 나머지 셀 계산: 왼쪽 및 위쪽 셀의 경로 수를 합산
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 현재 셀이 웅덩이인 경우 무시
                if (map[i][j] == -1) continue;
                
                // 왼쪽 셀에서 오는 경로 추가 (왼쪽 셀이 웅덩이가 아닌 경우)
                if (j-1 >= 0 && map[i][j-1] != -1) {
                    map[i][j] += map[i][j-1];
                }
                
                // 위쪽 셀에서 오는 경로 추가 (위쪽 셀이 웅덩이가 아닌 경우)
                if (i-1 >= 0 && map[i-1][j] != -1) {
                    map[i][j] += map[i-1][j];
                }
                // 경로 수는 큰 수를 피하기 위해 1,000,000,007로 나머지 연산 수행
                map[i][j] %= 1000000007;
            }
        }
        
        // 도착 지점의 경로 수 반환
        return map[m-1][n-1];
    }
}