백준 10971번 JavaScript

백준10971번 node.js

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
let visited = new Array(n).fill(false); //0번째 도시부터 n-1번째 도시 방문 여부 확인할 배열

let arr = Array.from(Array(n), () => new Array(n).fill(null));
for (let i = 0; i < n; i += 1) {
  const first = input[i + 1].split(" ").map(Number);
  for (let j = 0; j < n; j += 1) {
    arr[i][j] = first[j];
  }
}

const list = [];
let selected = [];
const dfs = (depth) => {
  if (depth === n) {
    let result = 0;
    for (let i = 0; i < n; i += 1) {
      let start = selected[i]; //출발하는 도시
      let end = selected[i + 1]; //도착하는 도시
      //맨 마지막 도시인 경우, 맨 처음 도시로 가는 경로 설정
      if (end === undefined) end = selected[0];

      //i에서 j로 가는 길이 없는 경우 예외처리
      if (arr[start][end] !== 0) {
        result += arr[start][end];
      } else return;
    }
    list.push(result);
    return;
  }

  for (let i = 0; i < n; i += 1) {
    if (visited[i]) continue; //방문했던 도시 제외
    visited[i] = true;
    selected.push(i);
    dfs(depth + 1);
    selected.pop();
    visited[i] = false;
  }
};

dfs(0);
const answer = Math.min(...list); //경우의 수들 중에서 가장 작은 값
console.log(answer);

중복 없이 모든 도시를 방문하는 경우의 수들을 구한 뒤 각각 비용을 계산해 주었습니다.
방문할 도시가 4곳이라면 [0,1,2,3],[0,1,3,2],[0,2,1,3]...
0,1,3,2의 순서로 방문한다면, (0,1) (1,3) (3,2) (2,0) 처럼 마지막에는 가장 처음 방문한 도시로 가는 비용을 계산해줍니다.

저는 예외처리를 깜박해서 디버깅 하는데에 좀 걸렸는데요.
i에서 j로 가는 길이 없는 경우도 고려해주어야 합니다.