[boj] 10971. 외판원 순회 2 (node.js)

문제

[boj] 10971. 외판원 순회 2 (node.js)

풀이

핵심 풀이

function rec(k, i, sum) {
  if (k + 1 == N) {
    return arr[i][0] === 0 ? 0 : (min = Math.min(min, sum + arr[i][0]));
  } else {
    for (let j = 0; j < N; j++) {
      if (visited[j]) continue;
      if (arr[i][j] === 0) continue;
      visited[j] = 1;
      rec(k + 1, j, sum + arr[i][j]);
      visited[j] = 0;
    }
  }
}

• rec() 함수로 브루트포스를 구현했다. i -> j 도시로 이동 불가능한 경우는 모두 반환처리해주고, visited 배열을 이용해 방문 여부를 표시한다. 배열을 함수 외부에 두고 인덱스로 접근해서 반환하는 경우는 0으로 방문 처리를 지워준다.

틀렸던 이유

• 푸는 것보다, 아래 정리한 틀린 이유 중 1, 2, 4번이 이 문제를 틀리는 대표적인 이유일 텐데, 나는 이 세가지를 모두 틀렸다. 1, 2번째 실수는 금방 바로잡았으나 3번째 코드의 오류와, 4번째는 집중력이 깨진 이후로 찾기 어려웠다.

1. min 값을 작게 잡았다.
2. return 시에 (마지막 도시에 방문 불가능한 경우도 있으므로) 0인 경우를 조건으로 걸어 반환해주어야 한다.
3. 순서 오류: continue 문 이전에 방문 표시 를 해서, 방문 표시를 지우지 않는 경우를 만드는 실수를 했다. 찾고는 바로 고쳤지만, 완벽하게 작성했다고 생각해서 기존에 작성된 코드가 언제 바뀌었는지도 몰랐다. 과도한 확신은 독이다!!!
4. if () 종료문 이외에 불필요한 순회로 인해 런타임에러 발생 -> else 문으로 묶어줘서 해결

• 브루트포스 유형은 틀리는 이유가 거기서 거기다. 정리해본 이유들이 모두 처음 보는 틀린 이유가 아닌데도 계속 틀린다. 내 집중력과 실력이 멈춰 있는 이유는 아마도, 이런 부분에서 매번 같은 실수를 반복하기 때문인 것 같다... 이제는 정면으로 마주하고 !! 다시는 실수하지 않도록 확실히 알고 넘어가기. 알고리즘을 맞게 짠 것 같아도, 사소한 부분에서 완전탐색의 경우의 수가 하나라도 엇나가면 그건 틀린 문제다. 한 번 할 때 꼼꼼히 보자!!! 제발... T-T

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = +input();
  const arr = [];
  for (let i = 0; i < N; i++) arr[i] = input().split(" ").map(Number);

  let min = 10 ** 10;
  let visited = [];
  visited[0] = 1;
  rec(0, 0, 0);
  console.log(min);

  function rec(k, i, sum) {
    if (k + 1 == N) {
      return arr[i][0] === 0 ? 0 : (min = Math.min(min, sum + arr[i][0]));
    } else {
      for (let j = 0; j < N; j++) {
        if (visited[j]) continue;
        if (arr[i][j] === 0) continue;
        visited[j] = 1;
        rec(k + 1, j, sum + arr[i][j]);
        visited[j] = 0;
      }
    }
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});