[백준 - node.js] 외판원 순회2 10971번

문제 설명

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

---

문제 풀이

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

let input = [];
let n = 0;
let count = 0;

rl.on('line', function (line) {
  if (!count) {
    n = +line;
  } else {
    input.push(line.split(' ').map(e => +e));
  }
  count++;
}).on('close', function () {
  solution(input);
  process.exit();
});

const solution = input => {
  // 초기세팅
  const visited = new Array(n).fill(false);
  const arr = [];
  let sum = 0;
  let min = Infinity;

  // dfs
  const dfs = count => {
    // base case => 다 돈 경우
    if (count === n) {
      let lastIdx = arr[arr.length - 1].index;
      let firstIdx = arr[0].index;
      let backCost = input[lastIdx][firstIdx];
      // 시작 지점의 비용을 제외하고 1부터 시작
      for (let i = 1; i < n; i++) {
        sum += arr[i].cost;
      }
      // 돌아가는 비용이 0이 아닌 경우에 마지막 -> 처음으로 돌아가는 비용을 더해줌
      if (backCost !== 0) {
        sum += +input[lastIdx][firstIdx];
      } else {
        sum = Infinity;
      }
	  // 최솟값 구함
      min = Math.min(sum, min);
      sum = 0;
    }
    
	// 순회 시작
    for (let i = 0; i < n; i++) {
    // 이전 지점의 인덱스를 통하여 다음 루트의 비용을 계산
    // 첫번째 지점의 prevIdx는 계산에 사용되지 않기 때문에 임의의 수 0으로 지정
      let prevIdx = arr[arr.length - 1] ? arr[arr.length - 1].index : 0;
      // 방문X && 자신X && 다음 지점의 값이 0이 아니라면 백트래킹 진행
      if (!visited[i] && count !== i && input[prevIdx][i] !== 0) {
        arr.push({ index: i, cost: input[prevIdx][i] });
        visited[i] = true;	
        dfs(count + 1);
        arr.pop();
        visited[i] = false;
      }
    }
  };

  dfs(0);
  console.log(min);
};