[백준 node.js / javascript] 진우의 달 여행(17484)문제

---

문제:

우주비행이 꿈이었던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

 

 

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두 번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느 위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

입력:

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.

다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.

출력:

달 여행에 필요한 최소 연료의 값을 출력한다.

---

 코드:

const fs = require("fs");
const input = fs
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n")
	.map((v) => v.split(" "));
const [N, M] = input[0].map((n) => Number(n));
const map = input.splice(1).map((v) => v.map((v) => Number(v)));
let sums = [];

function dfs(y, x, prevDirection, sum) {
	let directionX = [-1, 0, 1];

	if (x === -1 || x === M) return 0;
	sum += map[y][x];
	if (y === N - 1) return sums.push(sum);
	for (let i = 0; i < 3; i++) {
		if (prevDirection != directionX[i])
			dfs(y + 1, x + directionX[i], directionX[i], sum);
	}
}

for (let col = 0; col < M; col++) {
	dfs(0, col, -2, 0);
}

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

 

코드 설명:

출발지점은 첫 번째 row이기 때문에 map[0]열을 다 돌면서 각 idx의 시작지점으로부터 가능한 모든 경로를 탐색하기 위해 DFS 알고리즘을 사용했다.

 

dfs(Y, X, prevDirection, sum)

for (let col = 0; col < M; col++) {
	dfs(0, col, -2, 0);
}

 

진우는 한번 이전에 이동한 방향으로 연속으로 갈 수 없기 때문에 dfs를 돌 때 이전방향을 함께 보내주고 해당 좌표에서 사용한 연료를 더해서 같이 파라미터로 전달해 준다.

여기서 directionX는 진우가 이동할 방향이다

{

     -1 : 왼쪽 아래,

      0 : 아래,

       1 : 오른쪽 아래,

}

이때 x가 map배열 범위를 넘어서면 안 되므로 return

아니라면 연료를 sum에 더해주고 y가 map배열의 끝열에 다다르면 도착이므로 sums 배열의 해당 경로의 총연료를 push 해준다.

function dfs(y, x, prevDirection, sum) {
	let directionX = [-1, 0, 1];

	if (x === -1 || x === M) return 0;
	sum += map[y][x];
	if (y === N - 1) return sums.push(sum);
	for (let i = 0; i < 3; i++) {
		if (prevDirection != directionX[i])
			dfs(y + 1, x + directionX[i], directionX[i], sum);
	}
}

 

 

그렇게 모든 경로를 다 탐색하고 sums배열의 최소값을 찾아서 출력해 주면 끝이다.

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