[Java] 프로그래머스 - 등굣길 (3단계)

📝 문제

프로그래머스 > 코딩테스트 연습 > 동적계획법(Dynamic Programming)
등굣길

---

📝 답안

📌 작성 코드

import java.util.*;
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[m+1][n+1];
        boolean[][] check = new boolean[m+1][n+1];
        
        for (int i = 0; i < puddles.length; i++) {
            int x = puddles[i][0];
            int y = puddles[i][1];
            check[x][y] = true;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (check[i][j]) continue;
                
                if (i == 1 && j == 1) {
                    map[i][j] = 1;
                } else {
                    map[i][j] = (map[i-1][j] + map[i][j-1]) % 1000000007;
                }
            }
        }
        
        return map[m][n] % 1000000007;
    }
}

---

📌 결과

정확성 테스트

테스트 1 〉 통과 (0.04ms, 73.6MB)
테스트 2 〉 통과 (0.03ms, 77.3MB)
테스트 3 〉 통과 (0.03ms, 73.7MB)
테스트 4 〉 통과 (0.03ms, 77.9MB)
테스트 5 〉 통과 (0.04ms, 72.9MB)
테스트 6 〉 통과 (0.03ms, 74.1MB)
테스트 7 〉 통과 (0.05ms, 72.6MB)
테스트 8 〉 통과 (0.04ms, 76.8MB)
테스트 9 〉 통과 (0.04ms, 77.8MB)
테스트 10 〉 통과 (0.03ms, 72.7MB)

효율성 테스트

테스트 1 〉 통과 (0.61ms, 52.1MB)
테스트 2 〉 통과 (0.18ms, 53.1MB)
테스트 3 〉 통과 (0.37ms, 51.8MB)
테스트 4 〉 통과 (0.49ms, 52MB)
테스트 5 〉 통과 (0.43ms, 52.1MB)
테스트 6 〉 통과 (0.70ms, 52.7MB)
테스트 7 〉 통과 (0.38ms, 51.7MB)
테스트 8 〉 통과 (0.51ms, 52.3MB)
테스트 9 〉 통과 (0.56ms, 52.1MB)
테스트 10 〉 통과 (0.46ms, 52.4MB)

---

📌 코드 풀이

int[][] map = new int[m+1][n+1];
boolean[][] check = new boolean[m+1][n+1];

• map : 동적 계획법을 계산할 2차원 배열
• check : 물이 고인 위치를 체크할 2차원 배열

for (int i = 0; i < puddles.length; i++) {
	int x = puddles[i][0];
	int y = puddles[i][1];
	check[x][y] = true;
}

• puddles를 for문을 이용하여 물 웅덩이 위치 check 배열에 체크하기

for (int i = 1; i <= m; i++) {
	for (int j = 1; j <= n; j++) {
		if (check[i][j]) continue;
		if (i == 1 && j == 1) {
			map[i][j] = 1;
		} else {
			map[i][j] = (map[i-1][j] + map[i][j-1]) % 1000000007;
		}
	}
}

• 이중 for문으로 한 칸씩 오른쪽으로 이동하면서 계산하고, 아래 줄로 이동하기

---

📌 설명 한 눈에 파악하기