[Programmers] 등굣길 (Python, Java)

📖문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

✨핵심 내용 

"오른쪽과 아래쪽"으로만 움직여
집에서 학교까지 갈 수 있는 최단경로의 개수를 "1,000,000,007"로 나눈 나머지 return

🤔해결 아이디어 

유형: DP

현재 위치(i, j)에서 경로의 값이 최대가 되려면 왼쪽(i, j-1) 혹은 위(i-1, j)에서 와야 한다 

🟡dp 구조

1. dp 정의 

- (i, j) 위치까지 올 수 있는 최단 경로의 개수 

 

2. dp 초기화 

- 집의 위치: (0, 0)

- 위에서만 접근 가능한 위치 (왼쪽에서 올 수 없는 위치): (i, 0)

- 왼쪽에서만 접근 가능한 위치 (위에서 올 수 없는 위치): (0, j)

 

3. 점화식 

if (웅덩이가 아니면):
	dp[i][j] = dp[i][j-1] + dp[i-1][j]

 

🟡주의할 것

1. puddles은 행과 열의 위치가 바뀌어 전달된다

2. % 연산을 해서 return 해야 한다 (문제 조건 잘 읽기)

- 연산 중간에 % 연산을 해 주어야 시간 초과가 나지 않는다 (모듈러 연산 법칙 활용)

 

+) 모듈러 연산 법칙

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

---

✅정답 코드 (Python)

def solution(m, n, puddles):
    # 0. board 채우기 (1: 웅덩이)
    board = [[0 for _ in range(m)] for _ in range(n)]

    for p in puddles:
        if p != []:
            board[p[1] - 1][p[0] - 1] = 1

    # 1.dp 정의
    dp = [[0 for _ in range(m)] for _ in range(n)]

    # 2. 초기화
    # 2-1. 원점 - 출발 지점에는 웅덩이가 없음
    dp[0][0] = 1

	# 2-2. (i, 0) - 위에서만 올 수 있음
    for i in range(n):
        if board[i][0]:
            break
        dp[i][0] = 1

	# 2-2. (0, j) - 왼쪽에서만 올 수 있음
    for j in range(m):
        if board[0][j]:
            break
        dp[0][j] = 1

    # 3. 점화식
    for i in range(1, n):
        for j in range(1, m):
        	# 왼쪽, 위쪽에서 온 값 더하기
            if not board[i][j]: # 웅덩이라면 
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000007
	
    // 4. output
    return dp[n - 1][m - 1] % 1000000007

✅정답 코드 (Java)

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        // 0. board 채우기 (1: 웅덩이)
        int[][] board = new int[n][m];
        if (puddles[0].length > 0){
            for (int i = 0 ; i < puddles.length; i++) {
                board[puddles[i][1] - 1][puddles[i][0] - 1] = 1;
            }
        }        
                
        // 1. dp 정의 
        int[][] dp = new int[n][m];
        
        // 2. 초기화
        // 2-1. 원점 - 출발 지점에는 웅덩이가 없음
        dp[0][0] = 1;
        
        // 2-2. (i, 0) - 위에서만 올 수 있음
        for (int i = 0 ; i < n; i++) {
            if (board[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
            
        
        // 2-2. (0, j) - 왼쪽에서만 올 수 있음
        for (int j = 0 ; j < m; j++){
            if(board[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
            
        
        // 3. 점화식 
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 왼쪽, 위쪽에서 온 값 더하기
                if (board[i][j] == 0) // 웅덩이라면 비워두기
                    dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000007;
            }
        }
        
        // debug - 그대로 제출하면 시간 초과 (주의)
        // for (int i = 0 ; i < n; i++) {
        //     for (int j = 0 ; j < m; j++) {
        //         System.out.printf("%d ", dp[i][j]);
        //     }
        //     System.out.println();
        // }
        
        // 4. output
        return dp[n-1][m-1] % 1000000007;
    }
}