이번 글에서는 동적 계획법(Dynamic Programming)을 활용해 2차원 격자 위에서 시작점부터 끝점까지 갈 수 있는 고유한 경로의 개수를 구하는 방법을 알아보겠습니다.
문제 정의
m × n 크기의 2차원 배열(격자)이 있다고 가정해 봅시다. 한 사람은 왼쪽 상단의 시작 블록인 (0, 0)에서 출발하여 오른쪽 하단의 마지막 블록까지 이동하려고 합니다.
여기에는 하나의 제약 조건이 있습니다. 바로 한 번에 한 칸씩 아래로 또는 오른쪽으로만 이동할 수 있다는 것입니다.
우리는 격자의 높이(height)와 너비(width)를 인자로 받아서, 시작점에서 끝점까지 도달할 수 있는 서로 다른 경로의 총개수를 반환하는 JavaScript 함수를 작성해야 합니다.
접근 방식: 동적 계획법
핵심 아이디어는 간단합니다. 어떤 칸에 도달하는 경로의 수는 바로 위 칸까지의 경로 수와 바로 왼쪽 칸까지의 경로 수를 더한 값과 같습니다.
- 첫 번째 행과 첫 번째 열의 모든 칸은 한 가지 방법으로만 도달할 수 있으므로 값을 1로 초기화합니다.
- 나머지 칸은 위쪽 칸의 값과 왼쪽 칸의 값을 더하여 채워 나갑니다.
- 격자의 마지막 칸에 저장된 값이 곧 전체 고유 경로의 개수가 됩니다.
예제 코드
다음은 위 로직을 구현한 코드입니다.
const height = 3;
const width = 4;
const findUniquePath = (width = 1, height = 1) => {
// height × width 크기의 0으로 초기화된 2차원 배열 생성
const board = Array(height).fill(null).map(() => {
return Array(width).fill(0);
});
// 첫 번째 행과 첫 번째 열은 경로가 1가지뿐이므로 1로 설정
for (let rowIndex = 0; rowIndex < height; rowIndex += 1) {
for (let columnIndex = 0; columnIndex < width; columnIndex += 1) {
if (rowIndex === 0 || columnIndex === 0) {
board[rowIndex][columnIndex] = 1;
}
}
}
// 각 칸의 경로 수 = 위쪽 칸의 경로 수 + 왼쪽 칸의 경로 수
for (let rowIndex = 1; rowIndex < height; rowIndex += 1) {
for (let columnIndex = 1; columnIndex < width; columnIndex += 1) {
const uniquesFromTop = board[rowIndex - 1][columnIndex];
const uniquesFromLeft = board[rowIndex][columnIndex - 1];
board[rowIndex][columnIndex] = uniquesFromTop + uniquesFromLeft;
}
}
return board[height - 1][width - 1];
};
console.log(findUniquePath(width, height));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
10
결과 해석
3 × 4 격자에서는 총 10가지의 고유한 경로가 존재합니다. 실제로 이 문제는 조합론으로도 검증할 수 있습니다. 아래 또는 오른쪽 이동이 총 (m − 1) + (n − 1)번 필요하고, 그중 아래 이동의 위치를 선택하는 것이므로 C(m + n − 2, m − 1) = C(5, 2) = 10으로 동일한 결과를 얻을 수 있습니다.
이 알고리즘의 시간 복잡도는 O(m × n), 공간 복잡도 역시 O(m × n)입니다. 만약 공간을 절약하고 싶다면 1차원 배열만 사용하는 최적화 기법을 적용할 수도 있습니다.