외판원 순회 - DP와 비트마스킹 (백준 2098, node.js)

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

 

✦ 문제 이해

[가장 적은 비용을 들여 도시를 모두 순회하기]

1번부터 N번까지의 도시가 있다.

도시들 사이에는 길이 있고 길이 없을 수도 있다.

외판원은 1번 도시에서 시작해서 모든 도시를 순회한 뒤, 다시 처음 도시로 돌아온다.

단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)

이때, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

 

[각 도시간 이동 비용 행렬]

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다.

W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.

W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

 

✦ 입력

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

 

✦ 출력

35

 

 

✦ 풀이

 

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

function solution(arr) {
  const N = Number(input.shift());
  const W = input.map(row => row.split(' ').map(Number));

  // DP 배열: dp[visited][current] = 현재 도시에서 시작하여 모든 도시를 방문하는 최소 비용
  const dp = Array.from({length: 1 << N}, () => Array(N).fill(Infinity));
  console.log(dp);

  // 초기값 설정: 시작점을 방문한 상태에서 출발
  dp[1][0] = 0;

  // bottom-up 방식
  for (let visited = 1; visited < (1 << N); visited++) {
    for (let current = 0; current < N; current++) {
      if (!(visited & (1 << current))) continue; // 현재 도시를 방문하지 않은 경우 건너뛰기

      for (let next = 0; next < N; next++) {
        if (visited & (1 << next) || W[current][next] === 0) continue; // 이미 방문했거나 길이 없는 경우 건너뛰기

        const newVisited = visited | (1 << next); // 방문 상태 업데이트
        dp[newVisited][next] = Math.min(dp[newVisited][next], dp[visited][current] + W[current][next]);
      }
    }
  }

  // 모든 도시를 방문한 후 원래 도시(0)로 돌아오는 최소 비용 계산
  let minCost = Infinity;
  for (let last = 1; last < N; last++) {
    if (W[last][0] !== 0) { // 길이 있을 경우에만 최소 비용 계산
      minCost = Math.min(minCost, dp[(1 << N) - 1][last] + W[last][0]);
    }
  }
  return minCost;
}


console.log(solution(input));

 

DP 배열

• dp[visited][current]는 특정 상태(visited)에서 현재 도시(current)까지 모든 방문을 끝냈을 때의 최소 비용을 저장하는 배열이다.
• visited는 비트마스크로 표현되며, 예를 들어 0110(2)은 2번과 3번 도시를 방문한 상태를 뜻한다.
• 모든 가능한 방문 상태는 0001부터 1111(2)까지로, 최대 2^N의 경우의 수를 따진다.

초기값 설정

• dp[1][0] = 0으로 설정. 이는 1번 도시에서 출발하여 1번 도시만 방문한 상태에서의 비용이 0이라는 의미이다.

Bottom-Up 방식으로 DP 채우기

• visited는 방문 상태를 나타내는 비트마스크이다. 각 상태에서 현재 방문한 도시(current)를 기준으로 다른 도시(next)로 이동할 때의 최소 비용을 계산한다.

조건 확인

• 현재 도시 current가 이미 방문된 상태여야 하며, 다음 방문할 도시 next는 아직 방문하지 않은 상태여야 한다.
• 방문 상태를 업데이트하여 새로운 상태의 최소 비용을 저장한다.

최종 최소 비용 계산

• 모든 도시를 방문한 후 다시 출발 도시(0)으로 돌아오는 비용을 계산하여 minCost를 업데이트한다.