[JavaScript] 백준 2169번: 로봇 조종하기 (DP)

난이도 : 골드 2
알고리즘 유형 : 다이나믹 프로그래밍(DP)
문제 링크 : https://www.acmicpc.net/problem/2169

 

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력

첫째 줄에 최대 가치의 합을 출력한다.

 

 

문제 풀이

• 메인 생각 : 다이나믹 프로그래밍을 이용하며, DFS를 이용하여 최댓값을 찾아간다.

단순하게 완전탐색으로 문제를 풀면 최악의 경우 $ 3^{1000 * 1000} $의 계산을 요구하여 시간초과가 발생한다.
이전에 구한 값을 저장하여 반복 계산을 줄여 계산 시간을 줄일 것 이다.

 

이전에 구한 값들은 cost 라는 3차원 변수이다. 일반 2차원 변수가 아닌 3차원인 이유는 row index, colum index에 더해 들어온 방향을  저장하기 위해서이다.

방향까지 저장하는 이유는 어떤 방향에서 들어왔는지에 따라 계산할 수 있는 모양이 다르기 때문이다.

 

이후 저장할 값을 정했다면 DFS를 통해 각 칸들을 탐사하면 된다.

 

 

코드

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

const [N, M] = input.shift().split(" ").map(Number);
const map = input.map((row) => row.split(" ").map(Number));

const cost = Array.from({length: N}, () => Array.from({length: M}, () => Array.from({length: 3}, () => -Infinity)));
const visited =  Array.from({length: N}, () => Array.from({length: M}, () => false));

const di = [0, 1, 0];
const dj = [-1, 0, 1];

console.log(DFS(0, 0, 0));

function DFS(ci, cj, dir) {
  if(ci === N-1 && cj === M-1) return map[ci][cj];
  if(cost[ci][cj][dir] !== -Infinity) return cost[ci][cj][dir];

  visited[ci][cj] = true;

  let answer = -Infinity;

  for(let k=0; k<3; k++){
    const ni = ci + di[k], nj = cj + dj[k];

    if(0 > ni || ni >= N || 0 > nj || nj >= M) continue;
    if(visited[ni][nj]) continue;

    answer = Math.max(answer, DFS(ni, nj, k));
  }

  visited[ci][cj] = false;
  cost[ci][cj][dir] = answer + map[ci][cj];
  return cost[ci][cj][dir]; 
}

 

 

회고

처음에는 Priority Queue를 이용해서 풀 생각이었다. 하지만 최솟값이 아닌 최댓값을 찾는 문제여서 Priority Queue를 이용하여 푸는 것은 완전 탐색과 다를 바 없어졌다...

완전 탐색에서 시간 줄이는 법을 알게된 것 같아 좋다!