프로그래머스: 등굣길 (Dynamic Programming)
등굣길
m x n 의 격자 모양으로 표현된 길로 이동할 때,
puddles배열로 주어지는 물웅덩이를 피해 (m,n)에 위치한 학교로 가는 최단 경로 수 구하기제한 조건
1 ≤ m,n ≤ $10^2$문제 풀이 조건
m, n 모두 1로 주어지지는 않음.
물에 잠긴 지역은 0개 이상 10개 이하로, 이에 따라puddles배열의 길이도 0 이상 10 이하임.
집과 학교는 물에 잠기지 않음.
수가 커질 것에 대비해 결과는 1000000007으로 나눈 나머지로 반환할 것.
알고리즘 구상하기
문제 풀이에 집중한다.
문제에서 주어진 m x n의 길은 이중 배열로 표현할 수 있다. 이 때 m과 n의 최댓값은 $10^2$ 으로, 배열을 한 번 순회하는 경우에 대한 시간복잡도의 최대치는 $10^4$가 된다.
이에 따라 효율성 측면에서는 여유가 있다고 판단하였고 문제 풀이 방법을 찾는데 집중했다.
적절한 자료구조: Dynamic Programming
이 문제는 학창 시절 ‘확률과 통계’ 수학 문제를 풀며 한 번쯤은 접해봤을 유형이다.
이러한 최단경로 경우의 수 문제의 대표적인 풀이법에는 ‘순열로 식 세우기’, ‘매 길마다 최단 경로 수를 표시하여 이를 합산하기’ 등이 있는데, 이번 알고리즘 풀이에는 후자를 채택했다.
이 방법은 원하는 목적지에 도달하기까지 거치는 길마다 도달 루트의 경우의 수를 표시하고, 이를 원하는 목적지까지 계속해서 반복하며 누적하는 원리이다.
이는 Dynamic Programming의 원리와도 정확히 일치한다.
이에 따라 dp 라는 새로운 변수를 만들고 여기에 경로 수를 기록할 이중 배열을 만들어 할당했다. 그리고 m x n 만큼 반복문을 실행하여 dp에 최단 경로로 도달하는 경우의 수를 기록하여 Dynamic Programming을 구현했다.
물웅덩이 처리하기
이 문제는 ‘물웅덩이’라는 변수를 주고 있다.
물웅덩이가 존재하는 길은 지나갈 수 없기 때문에 사실상 없는 길이다.
이에 따라, 코드상에서 물웅덩이를 어떻게 구분하고 처리할 것인지 고민했다.
실제 수학 문제를 풀이하는 경우에는 직접 도식도를 그려, 장애물이 있는 길은 경로 수를 누적하지 않고 건너뛰었었다.
하지만 이번에는 코드를 작성하여 장애물이 있는 길을 체크하고 값을 누적하지 않도록 프로그래밍해 줘야 했다.
고민 끝에 초기 dp 배열을 설정할 때 배열 요소들을 null로 초기화 하도록 했다. 그리고 물웅덩이가 존재하는 구간은 이전 누계값에 상관없이 0으로 설정했다. 그 외 나머지 구간은 이전 경로에 도달하기까지의 경우의 수들을 더하여 정상적으로 합산하도록 반복문을 구현했다.
마지막으로 dp를 구현할 때 null 값의 여부를 체크하여 물웅덩이와 정상적인 길을 구분하고, 이전 경로의 경우의 수가 물웅덩이에 덮어 쓰이지 않도록 했다.
이를 종합하여 Dynamic Programming을 구현한 최종 결과는 다음과 같다.
[JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function solution(m, n, puddles) {
const dp = Array.from({ length: n }, () =>
Array.from({ length: m }, () => null)
);
dp[0][0] = 1;
puddles.forEach(([column, row]) => {
dp[row - 1][column - 1] = 0;
});
for (let row = 0; row <= n - 1; row += 1) {
for (let column = 0; column <= m - 1; column += 1) {
if (dp[row][column] === null) {
const top = row > 0 ? dp[row - 1][column] : 0;
const left = column > 0 ? dp[row][column - 1] : 0;
dp[row][column] = (top + left) % 1000000007;
}
}
}
return dp[n - 1][m - 1];
}