백준 10971 외판원 순회 2

문제

제한 사항

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

입출력 예

예제 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1
35

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift();
let city = [];
for (let x of input) {
  city.push(x.split(" ").map((e) => +e));
}
console.log(city);
const solution = (n, city) => {
  let answer = [];
  let visited = new Array(n).fill(0);
  let tmp = [];
  const dfs = (cnt, curNode) => {
    if (cnt === n - 1) visited[0] = 0; // 다시 원래의 도시로 돌아 올 수 있게 하기 위해서
    if (cnt === n) {
      if (visited.every((e) => e === 1)) {
        // 모든 도시를 방문했다면! 누적한 비용의 합을 answer에 저장
        answer.push(tmp.reduce((a, c) => a + c, 0));
      }
    } else {
      for (let i = 0; i < n; i++) {
        if (!city[curNode][i]) continue; // 값이 없는 곳은 건너 뛴다.
        if (!visited[i] && curNode !== i) {
          // 방문한적이 없고 자기자신이 아닌곳은 방문
          visited[i] = 1;
          tmp.push(city[curNode][i]); // 비용을 tmp 배열에 누적
          dfs(cnt + 1, i);
          tmp.pop();
          visited[i] = 0;
        }
      }
    }
  };
  visited[0] = 1;
  dfs(0, 0);

  return Math.min(...answer);
};

console.log(solution(n, city));

• dfs에 약간의 아이디어를 더해 완성 시켰다. 매개변수를 활용해 문제를 쉽게 만들 수 있는 것을 기억하자.
• 주석에 설명을 달아뒀다.