[백준10971_자바스크립트(javascript)] - 외판원 순회 2

🔴 문제

외판원 순회 2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], ...costs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

let ans = Infinity;
let stack = [];
const bt = (cnt) => {
  if (stack.length === n) {
    const start = stack[0];
    const end = stack.at(-1);
    if (costs[end][start] === 0) return;

    ans = Math.min(ans, cnt + costs[end][start]);
    return;
  }

  for (let i = 0; i < n; i++) {
    if (stack.includes(i)) continue;
    const start = stack.at(-1);
    const end = i;

    const cost = costs[start][end];
    if (cost === 0) continue;
    stack.push(i);
    bt(cnt + costs[start][end]);
    stack.pop();
  }
};

for (let i = 0; i < n; i++) {
  stack.push(i);
  bt(0);
  stack = [];
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

외판원순회 TSP 문제다. 이 문제는 n의 범위가 10이다.
외판원이 모든 도시를 순회하는 방법. 즉 순열을 구해서 모든 경우의 수를 탐색한 뒤 최소값을 구해줘도 문제 없다.
만약 N의 범위가 커진다면 모든 경우의수를 제한시간내에 탐색하지 못하는데, 이 경우 비트마스킹 + dp를 사용해 최적화를 하면된다.

다시 이 문제로 돌아와서 모든 경우의수를 탐색해주기 위해 백트래킹을 구현하고, 전역변수의 스택으로 고른 순서를 관리한다. 스택의 길이가 N이라면 모든 경로를 탐색해줬기 때문에 지금까지 구한 cnt에 끝지점에서 시작지점으로 돌아가는 비용을 계산해서 정답 ans를 업데이트 한뒤 재귀호출을 종료한다.

n개의 도시를 다 고르지 못했다면 도시를 선택해주는데 이 때 이미 방문한 도시를 재방문하지 않기 위에 스택에 해당 도시가 들어있는지 아닌지 파악한 후, 코스트를 구해 갈 수 있다면 재귀호출을 수행해준면 된다.

🔵 Ref