[BOJ] 1520 내리막 길 (node.js)

BOJ 문제 1520번의 풀이 과정을 작성한 게시글입니다.

 

링크

https://www.acmicpc.net/problem/1520

 

 

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

 

 

 

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

 

풀이 과정

접근법: dp

여기서 구하고자 하는 값은 (0, 0)에서 출발했을 때 (N-1, M-1)까지 갈 수 있는 경로의 갯수이다.

가장 단순하게는 모든 구간에서 상하좌우로 탐색하는 경우를 생각할 수 있는데, 그 경우 최대 4^500x500의 연산이 수행되므로 시간 초과가 발생한다.

 

따라서 dp를 통해 연산량을 최적화 해야한다.

문제를 통해 알 수 있는 것은 항상 본인보다 더 낮은 위치로 이동한다는 점이다.

따라서 지도를 통해 규칙을 파악해보면 모든 좌표에서 

현재 지점에서 갈 수 있는 경로의 수 = 더 낮은 높이로 이동했을 때 최종 목표에 도달할 수 있는 경로 개수의 합이 된다는 것을 알 수 있다.

 

예를 들어 아래와 같은 지도가 있다고 가정하자.

	1열	2열
1행	50	20
2행	40	10

 

그렇다면 최종적인 목표는 1행 1열에서 2행 2열까지 갈 수 있는 경로의 합을 구하는 것이다.

 

이때 dp 배열으로 최종 목표까지 도달할 수 있는 경로의 수를 저장하면 아래와 같다.

	1열	2열
1행	2	1
2행	1	1

 

 

즉, (1행 1열~2행 2열) 경로의 수 = (1행 2열~2행 2열) 경로의 수 +  (2행 1열~2행 2열) 경로의 수 인 것이다.

 

주의해야 할 점은 초기에 dp 배열에는 0이 아닌 값을 저장해야 한다는 점이다.

그 이유는 이미 방문했으나 경로가 0인 상태와 방문하지 않은 상태를 구분하기 위함이다.

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const map = input.slice(1).map((x) => x.split(" ").map(Number));

const dp = Array.from({ length: N }, () => Array(M).fill(-1)); // 경로 개수

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

const dfs = (x, y) => {
  if (x === N - 1 && y === M - 1) return (dp[x][y] = 1);

  if (dp[x][y] !== -1) return dp[x][y];

  dp[x][y] = 0;

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[x][y] <= map[nx][ny]) continue;

    dp[x][y] += dfs(nx, ny);
  }

  return dp[x][y];
};

dfs(0, 0);

console.log(dp[0][0]);

 

후기

한 번 풀었던 문제라 접근법이 바로 떠오른 문제였다.