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

🔴 문제

외판원 순회

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[N], ...W] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const dp = Array.from({ length: N }, () => Array(1 << (N - 1)).fill(0));

const TSP = (n, route) => {
  if (dp[n][route] !== 0) return dp[n][route];

  if (route === (1 << (N - 1)) - 1) return W[n][0] || Infinity;

  let min = Infinity;
  for (let i = 1; i < N; i++) {
    if (!W[n][i] || route & (1 << (i - 1))) continue;

    const distance = W[n][i] + TSP(i, route | (1 << (i - 1)));
    min = Math.min(distance, min);
  }

  dp[n][route] = min;

  return min;
};

console.log(TSP(0, 0));

🟢 풀이

⏰ 소요한 시간 : -

외판원 순회 문제다.
외판원 순회는 아래와 같은 조건을 만족하는 경우에서 최소 비용을 구하는 문제다.

• N개의 정점과 정점간의 특정비용이 존재한다.
• 특정 정점으로 이동하지 못하는 경우도 생기며, 이 경우 비용은 0이다. 즉 길이 없을 수도 있다는 의미
• 출발도시는 0번 도시로 고정되며 모든 도시를 한번씩 다 방문하고 원래도시로 복귀해야 한다.

위 조건을 모두 만족할 경우 외판원 순회로 풀이하는 것을 고려해볼 수 있다.

여튼... 이 문제를 완전 탐색으로 풀이한다면?
사실 상 순열을 구하게 된다. 즉 O(N!)의 시간복잡도를 가지게 된다.
따라서 비트마스킹 기법을 사용해 방문 여부를 확인하고, 특정 정점까지의 방문상태가 겹친다면 재귀호출 없이 DP를 사용해 최적화한다.

DP는 아래와 같이 정의한다.

// N : 현재 방문중인 정점의 번호
// Route : 현재까지 방문한 도시들의 비트 집합
// Route 경로를 거쳐 N번째 정점을 방문중일 때 최소 비용
DP[N][route]

이제 코드를 살펴보자! dp 배열은 모두 0으로 초기화 한다.

if (dp[n][route] !== 0) return dp[n][route];

만약 현재 경로를 이전에 탐색한 적이 있다면 0이 아닐테니 그대로 리턴해준다.

if (route === (1 << (N - 1)) - 1) return W[n][0] || Infinity;

만약 모든 정점을 한번씩 다 방문한 경우에는 현재있는 위치 N에서 처음 시작위치인 0으로 돌아갈 수 잇는지를 확인한다. 돌아갈 수 있따면 W[n][0]을 리턴하고, 아니라면 무한대를 리턴한다.

let min = Infinity;
for (let i = 1; i < N; i++) {
  if (!W[n][i] || route & (1 << (i - 1))) continue;

  const distance = W[n][i] + TSP(i, route | (1 << (i - 1)));
    min = Math.min(distance, min);
}

그 후 이제 최단거리를 구해주면 되는데, 0번노드에서 시작했으니 1번 노드부터 까지 반복하며 현재노드에서 다음노드로 가는 거리 + 재귀 로직을 수행해준다.
이 거리를 min값과 비교하며 최소값을 갱신하면 된다.

🔵 Ref