[백준 / javascript] 17484 진우의 달 여행(small)

문제 설명)

 

🌙 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙할 때 연료의 최소값을 구하는 문제 

 

조건 ) 우주선이 움직일 수 있는 방향은 다음과 같고, 두번 연속 같은 방향으로 움직일 수 없다

 

풀이)

 

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((arr) => arr.split(" ").map((a) => Number(a)));

const num = input[0];

let min = [];


function check_min(prev, i, j, sum) {
  if (i === num[0]) {
    sum += input[i][j];
    min.push(sum);
    return;
  }
  sum += input[i][j];
  if (prev != -1 && j > 0) check_min(-1, i + 1, j - 1, sum);
  if (prev != 1 && j + 1 < num[1]) check_min(1, i + 1, j + 1, sum);
  if (prev != 0) check_min(0, i + 1, j, sum);
  return;
}

for (let i = 0; i < num[1]; i++) {
  check_min(2, 1, i, 0);
}

console.log(Math.min(...min));

 

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M이 주어지고 다음 N줄 동안 각 행렬의 원소 값이 주어짐

-> 문자열로 읽은 값들을 정수 이차원 배열로 파싱!

(나는 아직 js초보라 초반에 값들을 정수로 안바꿔줘서 이상한 결과가 나왔었다ㅎ..ㅎ)

 

나는 우선 갈 수 있는 모든 경우의 수에 대한 연료값을 재귀함수인 check_min함수(dfs알고리즘)를 통해 구해주었다

function check_min(prev, i, j, sum) {
  if (i === num[0]) {
    sum += input[i][j];
    min.push(sum);
    return;
  }
  sum += input[i][j];
  if (prev != -1 && j > 0) check_min(-1, i + 1, j - 1, sum);
  if (prev != 1 && j + 1 < num[1]) check_min(1, i + 1, j + 1, sum);
  if (prev != 0) check_min(0, i + 1, j, sum);
  return;
}

  

재귀함수 안에서는 i가 num[0](행의 크기)인지 즉, 달에 도착했는지 확인해주고 도착했을 경우 min배열에 sum을 push해준다.

아닌 경우 현재 좌표값을 더해주고 갈 수 있는 세가지 방향에 대해 prev(이전 방향으로 -1또는 0 또는 1)과 같지 않을 경우 check_min을 호출 해준다!

(처음에는 sum을 전역변수로 두고 매개변수로 두지 않았었는데 그랬다가 경우의 수에 따른 연료값이 아니라 모든 연료값이 더해졌다😅)

 

마지막으로 min배열에서 Math.min()함수를 이용해 최솟값을 출력해주면 끝XD!