문제링크

---

- 풀이

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

const N = Number(input.shift());

const cityArr = input.map((city) => city.split(" ").map(Number));

let visited = Array(N).fill(false);

let answer = Number.MAX_SAFE_INTEGER;

function dfs(depth, start, cost) {
  if (depth === N - 1 && cityArr[start][0] !== 0) {
    answer = Math.min(answer, cost + cityArr[start][0]);

    return;
  }

  for (let i = 0; i < N; i++) {
    if (visited[i] || cityArr[start][i] === 0) {
      continue;
    }

    visited[i] = true;
    dfs(depth + 1, i, cost + cityArr[start][i]);
    visited[i] = false;
  }
}

visited[0] = true;

dfs(0, 0, 0);

console.log(answer);

여기서 start는 시작도시, depth는 깊이, cost는 비용을 나타낸다.

그리고 반복문을 돌때의 i는 다음 방문할 도시의 인덱스를 나타낸다.

W[i][i]는 항상 0이고, 방문 불가능한 도시도 있으니 조건식에서 판별하여 방문 불가능한 도시는 넘겨준다.

그리고 최대 깊이에 도달했을때, 즉 출발도시로 돌아갈때 cityArr[start][0] !== 0 의 조건식을 통해서 이동할수 있는 칸으로 돌아가서 값을 구해준다.