[코딩테스트] Java 등굣길

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

어렸을 때에 수학 문제를 풀 때에 가장자리에 1씩 두고 중간 값은 같은 열 위의 행과 같은 행 왼쪽 열의 합을 더해주는 방식을 사용했습니다.

소스코드

import java.util.*;

class Solution {
    private final int MOD = 1000000007;
    private final int DISABLE = -1;

    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        for(int[] puddle: puddles) {
            dp[puddle[1]-1][puddle[0]-1] = DISABLE;
        }
        
        // init
        dp[0][0] = 1;
        for(int i = 1; i < m; i++) { // 가로
            if (dp[0][i] == DISABLE || dp[0][i-1] == DISABLE) {
                break;
            } else {
                dp[0][i] = 1;
            }
        }
        for(int i = 1; i < n; i++) { // 세로
            if (dp[i][0] == DISABLE || dp[i-1][0] == DISABLE) {
                break;
            } else {
                dp[i][0] = 1;
            }
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(dp[i][j] == DISABLE) continue;
                
                if (dp[i-1][j] == DISABLE) {
                    dp[i][j] = dp[i][j-1];
                } else if (dp[i][j-1] == DISABLE) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
                }
            }
        }
        
        return dp[n-1][m-1] % MOD;
    }
}

코드 설명

• int[][] dp = new int[n][m]; for(int[] puddle: puddles) { dp[puddle[1]-1][puddle[0]-1] = DISABLE; }
  
  • dp배열을 초기화합니다.
  • 웅덩이 위치에는 상수로 정의한 DISABLE로 설정합니다.
• 가장자리 초기화
  
  • 가로와 세로의 값을 초기화합니다.
  • 만약 웅덩이가 있다면 그 이후로는 처리를 하지 않습니다.

for(int i = 1; i < n; i++) {
    for(int j = 1; j < m; j++) {
        if(dp[i][j] == DISABLE) continue;
        
        if (dp[i-1][j] == DISABLE) {
            dp[i][j] = dp[i][j-1];
        } else if (dp[i][j-1] == DISABLE) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
        }
    }
}

• 현재 칸 (i, j)는 위 칸(dp[i-1][j])과 왼쪽 칸(dp[i][j-1])에서 올 수 있습니다.
• 웅덩이(DISABLE)가 있는 경우
  • 위 칸이 웅덩이면 왼쪽 경로만 고려합니다.
  • 왼쪽 칸이 웅덩이면 위쪽 경로만 고려합니다.
• dp[i][j]=(dp[i-1][j]%MOD+dp[i][j-1]%MOD)%MOD
  • 위와 왼쪽 모두 웅덩이가 아니라면 두 경로의 합을 계산합니다.
• return dp[n-1][m-1] % MOD;
  • 결과를 반환합니다.