[JS][백준]1520_내리막 길

문제 번호

1520번: 내리막 길

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

 

문제 풀이

 DFS와 DP를 사용해야하는 문제이다. 

처음에는 DFS를 돌면서 도착점에 도착했을 때 카운트를 해주고 해당 카운터를 반환했는데 이럴경우 시간 초과에 걸리게 된다. 그래서 중복되는 과정을 줄일 수 있도록 이전 값들을 활용해야 겠다고 생각했다. 여기서 고민을 했던 점은 같은 (x,y) 좌표에 도착하더라도 걸리는 '칸 수'는 다를 수 있다는 점이었다. 

 

우선 시작점에서 DFS를 수행한다. 그리고 갈 수 있는 다음 좌표들에서 다시 DFS를 수행한다. 이때 현 좌표에 각 DFS의 반환값들을 누적합으로 더해준다. sum 배열은 방법의 수를 나타내는 배열이다. 처음에는 모두 '-1' 로 초기화를 했기 때문에 아직 방문하지 않은 좌표라서 경로의 수를 구해야 한다면 `sum[curY][curX] = 0` 으로 방문 했음을 알림과 동시에 경로 갯수를 올바르게 구할 수 있도록 한다.

  // 방문 표시
  sum[curY][curX] = 0;
  for (let next = 0; next < 4; next++) {
    const [nextX, nextY] = [curX + dxy[next][1], curY + dxy[next][0]];
    if (
      nextX >= 0 &&
      nextX < N &&
      nextY >= 0 &&
      nextY < M &&
      map[curY][curX] > map[nextY][nextX]
    ) {
      sum[curY][curX] += backTracking(M, N, map, sum, dxy, nextX, nextY);
    }
  }

이 때 도착점에 도착하거나 이미 해당 좌표에서 DFS를 수행하였어서 계산 값이 있는 경우는 미리 반환해준다.

 if (curX === N - 1 && curY === M - 1) return 1;

  if (sum[curY][curX] !== -1) {
    return sum[curY][curX];
  }

이렇게 함으로써 이미 계산을 끝마친 출발지점에 대해서는 중복된 계산을 하지 않아도 된다. (x,y) 에서 (nextX, nextY)로 가는 방법은 1개 뿐이므로 도착지점에서 (x,y)까지 오는 방법은 (x,y)에서 갈 수 있는 좌표들에서 DFS를 돌려서 구할 수 있다. 주어진 문제는 (0,0)에서 (M,N)으로 가는것 이지만 실제로 우리가 채우는 배열(sum)의 각 좌표값이 나타내는 값은 (M,N)에서 해당 좌표까지 올 수 있는 방법의 수 개수이다. (i.e 좌표가 (3,5)이고 해당 값이 8이라면 (M,N)에서 (3,5)까지 올 수 있는 방법은 8개다!)

그래서 위의 과정을 모두 마치고 sum[0][0]을 출력해주면 된다.

 

전체코드

const main = () => {
  const input = require("fs").readFileSync("input.txt").toString().split("\n");
  const [M, N] = input[0].split(" ").map(Number);

  const map = input.slice(1, M + 1).map((_) => _.split(" ").map(Number));
  const sum = new Array(M).fill(null).map((_) => new Array(N).fill(-1));
  const dxy = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  console.log(backTracking(M, N, map, sum, dxy, 0, 0));

  return 0;
};

// 각 좌표마다 오는 방법이 몇개 인지 memo 하면서 가야할듯.

const backTracking = (M, N, map, sum, dxy, curX, curY) => {
  if (curX === N - 1 && curY === M - 1) return 1;

  if (sum[curY][curX] !== -1) {
    return sum[curY][curX];
  }

  // 방문 표시
  sum[curY][curX] = 0;
  for (let next = 0; next < 4; next++) {
    const [nextX, nextY] = [curX + dxy[next][1], curY + dxy[next][0]];
    if (
      nextX >= 0 &&
      nextX < N &&
      nextY >= 0 &&
      nextY < M &&
      map[curY][curX] > map[nextY][nextX]
    ) {
      sum[curY][curX] += backTracking(M, N, map, sum, dxy, nextX, nextY);
    }
  }

  return sum[curY][curX];
};

main();

특이사항

값들 메모 까지는 생각했는데 구체적인 방법을 떠올리는게 너무 어려웠다.