문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력

6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

예제 출력

29

내가 했던 풀이 방법

1. 두번째 줄부터 입력받은 원소 값들을 matrix에 저장해준다.
2. directions 배열을 [-1, 0, 1]로 만들어준다. 이때, -1은 왼쪽 대각선 방향 / 0은 아래 방향 / 1은 오른쪽 대각선 방향을 의미한다.
3. 지구 어디에서나 출발 가능하므로, 0부터 M-1까지 DFS를 수행한다. 이때, DFS에는 depth, direction, x, sum이 전달된다. (출발이므로 depth는 0, direction은 어디든 갈 수 있으므로 -2(directions 값만 아니면 뭐든 가능하다.), x는 현재 for문의 i값, sum은 초기값이므로 0을 넣어준다.)
4. DFS에서는 x값을 먼저 확인한다. 만약 x가 -1이나 M일 경우 그대로 해당 DFS를 끝내준다. (x는 -1이나 M이상이 될 수 없으므로) 그 뒤, sum에 현재 위치하는 공간의 값을 matrix에서 찾아 더해준다. depth가 N-1이라면(달에 도착) 현재까지의 sum을 sums 배열에 저장한 뒤 DFS를 끝내준다.
5. 다음 depth의 DFS를 호출하기 위해서는 이전에 가지 않은 방향으로 호출해주어야 한다. 즉, 현재 DFS의 direction값이 -1일 경우, -1로 호출해서는 안 된다. for문을 통해 directions를 순환하면서 현재 direction값과 같을 경우는 무시하고, 같지 않을 경우 depth를 +1, direction을 현재 directions[i]의 값, x를 현재 x에서 directions[i]를 더한 값을 넣어준다. (sum은 전달받은 sum을 그대로 전달해준다.)
6. 모든 DFS가 끝난 후, sums 배열에 최솟값을 출력해준다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = parseInt(n.trim().split(' ')[0]);
let M = parseInt(n.trim().split(' ')[1]);

let matrix = Array.from({ length: N }, () => new Array(M));

let line = [];
for (let i = 0; i < N; i++) {
  line = input[i].trim().split(' ');
  for (let j = 0; j < M; j++) {
    matrix[i][j] = parseInt(line[j]);
  }
}

let sums = [];
let directions = [-1, 0, 1];
function DFS(depth, direction, x, sum) {
  if (x === -1 || x === M) {
    return 0;
  }
  sum += matrix[depth][x];
  if (depth === N - 1) {
    sums.push(sum);
    return;
  }

  for (let i = 0; i < 3; i++) {
    if (direction === directions[i]) continue;
    DFS(depth + 1, directions[i], x + directions[i], sum);
  }
}

for (let i = 0; i < M; i++) {
  DFS(0, -2, i, 0);
}

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

회고

방법을 그냥 구현하면서 단단하게 만들어보려고 했는데 코드를 늘려갈 수록 점점 꼬이는 것 같아서 제대로 방법을 찾아서 풀이해야했다.. 알고리즘 찾기 정말 어려웠는데 DFS로 풀이하면 될 것 같은데 방향을 어떻게 연속되지 않게 이동할 수 있을까를 생각하느라 정말 머리가 빠질 뻔 했다.. 단순하게 방향을 변수로 넣어주면 되는것이긴 했는데.. 이를 해결하니 양끝 값은 어떻게 처리해주나도 참 고민이 됐는데.. 그냥 끝내버리면 되는 것이었다. 단순한 걸 되게 오래 고민했다. 아직 DFS 흐름에 대해 완벽하게 알지 못하는 것 같았다. 그래도 이 문제를 풀면서 DFS의 흐름을 좀 깨닳은 것 같다.. 요즘 DFS 문제를 많이 풀었는데 이제는 좀 깨우친 것 같다. 역시 안 풀릴 땐 해당 알고리즘 문제를 많이 풀어보는 게 정답이구만