외판원 순회 문제 [BOJ 2098 / Node.js]

Overview

외판원 문제는 $N$개의 도시가 주어질 때, 한 도시에서 출발해 모든 도시를 한번씩 방문하고 다시 출발점으로 돌아오는 가장 비용이 적은 경로를 찾는 문제입니다. 단순히 모든 경우를 고려하는 것은 문제의 제약사항으로 인해 시간초과가 발생하므로 여러 최적화 기법으로 해결하는 것이 관건입니다.

1. 시간 복잡도 줄이기

현재 다양한 알고리즘 문제를 풀고 정리해보면서, 공통적으로 적용하고 있는 문제 접근 방법은 아래와 같습니다.

문제 분석
    ↓
완전탐색 가능? → YES → 완전탐색
    ↓ NO
    ↓
부분 문제로 쪼개짐? → YES → DP 고려
    ↓              → 배열 크기 체크
    ↓                  ↓ 너무 크면
    ↓                  다른 방법
슬라이딩 윈도우/투 포인터?
    ↓
Greedy 가능?
    ↓
etc (그래프, 트리 등)

이 접근의 핵심은 처음에는 문제를 단순화하여 바라보고 그것이 되지 않는 경우를 고려해보면서 적절한 알고리즘을 찾아가는 것입니다.

먼저, 모든 경로를 탐색하며 최적해를 구하는 방법을 생각해봅시다. 이 경우 그래프 탐색을 위해 DFS를 사용하는 경우, $N$개의 도시를 나열하는 모든 순열을 탐색하므로 시간 복잡도가 $O(N!)$가 됩니다. $N$이 16만 되어도 $16!$은 조 단위를 훌쩍 넘어가므로 시간 내에 절대 풀 수 없습니다.

완전탐색이 안된다는 것을 알았으니, 그 다음에는 부분 문제로 이 과정을 쪼개어 바라봤을 때 아래와 같이 부분 문제 사이에서 중복이 발생하는 것을 발견할 수 있습니다.

• 0->1->2 순서로 방문했든 0->2->1 순서로 방문했든, “현재 1번 도시에 있고, {0, 1, 2} 집합을 방문한 상태”는 동일합니다.
• 따라서 이 상태에서 남은 도시들을 방문하는 최소 비용은 이전에 어떤 순서로 왔는지와 상관없이 항상 같습니다.

과정 중 중복이 발생하는 경우는 곧 메모이제이션을 통해서 최적화가 가능하다는 것입니다. DP를 통해서 해결이 가능하다고 판단내릴 수 있습니다. 저도 처음에는 곧바로 이런 부분 문제에 대한 관계점을 포착하는 것에 어려움을 겪었습니다. DP의 어려운 점은 어떤 상태를 관리할 것인가에 있다고 생각하는데, 이 감을 익히려면 DP 문제들을 풀어보면서 채워야하는 것 같습니다.

돌아와서, 위와 같은 겹치는 부분 문제를 발견했으니 그 부분 문제를 유일하게 정의할 수 있는 변수들이 무엇인지 생각해봐야 합니다. 즉, 문제를 풀기 위해 꼭 필요한 변하는 값은 무엇인지 생각해봤을 때,

1. ‘현재 어느 도시에 있는가’는 다음 도시를 탐색해 나가기 위해서 꼭 필요하고,
2. ‘지금까지 방문한 도시’는 다음 도시가 방문한 곳인지 아닌지 판단하기 위해 꼭 필요합니다.

따라서 문제를 풀기 위해 필수적인 두 개의 변수를 DP 상태로 정의할 수 있습니다. 탑다운의 관점으로, 재귀 호출을 통해 푼다고 생각하면 아래와 같이 dp 배열을 정의해볼 수 있겠네요.

dp[current][visited] = “현재 current 도시에 있고, visited 집합의 도시들을 모두 방문했을 때, 아직 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발점(0번)으로 돌아가는 데 드는 최소 비용”

탑다운 방식은 미래의 비용을 정의하기 때문에, 현재 까지의 최소비용이 아닌 지금까지의 상태를 토대로 나머지 도시들을 모두 방문했을 때 최소 비용으로 정의할 수 있습니다.

시간 복잡도를 계산해보면 다음과 같습니다.

1. 총 상태의 개수 ($O(N \cdot 2^N)$):
   • current (현재 도시): $N$ 가지
   • visited (방문 집합): $2^N$ 가지
     • N개의 도시에 대해 방문/미방문 두 개의 상태 중 하나를 저장하면 $2^N$ 이 됩니다.
2. 하나의 상태를 계산하는 시간 ($O(N)$):
   • dp[curr][vis] 값 하나를 구하기 위해, 다음 도시를 찾는 반복문을 $N$번 돕니다.

총 시간 복잡도 = (상태 개수) $\times$ (상태 계산 시간) = $O(N^2 \cdot 2^N)$ 문제의 상한선인 N이 16일 때를 대입했을 때 16,777,216으로 천만 단위이기 기존 조 단위었던 시간 복잡도에서 많이 최적화가 된 것을 확인할 수 있습니다.

2. 비트마스크 적용

방금 정의한 dp 배열에서 visted는 방문한 도시들의 집합이었습니다. 일반적으로 visited를 작성할 때는 [true, false, true ...]와 같은 배열을 만들어서 관리하고는 합니다. 그런데 그 방법으로라면 dp[5][[true, false, true ...]] 와 같이 문법적으로 불가능한 코드가 됩니다.

따라서 Map이나 Object를 사용하는 방법으로, dp[5]["TFT..."] 처럼 문자열 키를 사용해 저장하는 방법이 있습니다만, 이는 모든 탐색에서 문자열을 다루는 과정이 포함되게 되므로 느리고 효율적이지 않습니다.

이 경우에서 상태를 효과적으로 다룰 수 있게 해주는 것이 비트마스크를 사용하는 방법입니다. dp[5][21]이라는 상태를 바라보면, 21은 이진법으로 10101이고 이는 1,3,5번째 비트가 1이므로 1,3,5번째 도시가 1, 즉 방문 되었다 라는 상태를 나타낼 수 있는 겁니다. 비트 연산은 $O(1)$의 속도로 상태를 읽고 쓸 수 있어서 매우 효율적입니다.

3. 정답 코드

function solve(input) {
  const n = Number(input.shift());
  const ALL_VIS = (1 << n) - 1;
  const path = input.map((v) => v.split(" ").map(Number));
  const START_NODE = 0;
  const dp = Array.from({ length: n }, () => new Array(ALL_VIS + 1).fill(0));

  function tsp(curr, vis) {
    if (vis === ALL_VIS) {
      if (path[curr][START_NODE] > 0) {
        return path[curr][START_NODE];
      }
      return Infinity;
    }

    if (dp[curr][vis] !== 0) {
      return dp[curr][vis];
    }

    dp[curr][vis] = Infinity;

    for (let i = 0; i < n; i++) {
      if (path[curr][i] === 0) continue;
      if (vis & (1 << i)) continue;
      const newVis = vis | (1 << i);
      const result = tsp(i, newVis);
      if (result === Infinity) continue;
      dp[curr][vis] = Math.min(dp[curr][vis], path[curr][i] + result);
    }

    return dp[curr][vis];
  }

  const result = tsp(START_NODE, 1 << START_NODE);
  console.log(result === Infinity ? 0 : result);
}

// == I/O ==
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

solve(input);

이 문제의 경우 특수하게도 시작점이 어떤 곳이 되어도 상관 없습니다. 외판원 순회 문제는 단순히 말하자면 사이클을 찾는 문제이고, 어떤 도시에서 출발하든, 최적의 사이클을 구성하는 경로의 집합 자체는 동일하기 때문입니다. 따라서 시작점에 대한 명시가 없는 문제이지만 0번 도시부터 순회를 시작해도 상관없습니다.

4. 재귀 동작 흐름 해설

아직 저는 재귀 + 메모이제이션을 통한 흐름이 아직 어색하게 느껴집니다. 재귀는 흐름을 하나씩 적어서 보면 탑다운 방식의 DP는 이런거구나 .. 하고 이해할 수 있습니다.

1. 시작: tsp(0, 1 << 0) 호출 (0번 도시, {0} 방문 상태)
2. 확인: dp[0][1]이 -1인지 확인 (계산한 적 없음)
3. 진입: dp[0][1] = Infinity로 설정
4. 탐색: for 루프로 next 도시 탐색 (예: next = 1)
5. 재귀: path[0][1] + tsp(1, 1 | (1 << 1))을 계산하기 위해 tsp(1, 3) 호출
6. (반복): 이 과정이 모든 도시를 방문할 때까지 깊이 들어갑니다.
7. Base Case: tsp(k, ALL_VIS) (모두 방문)가 호출되면, path[k][0] (0번으로 복귀하는 비용)을 반환합니다.
8. 복귀: tsp(k, ...)가 값을 반환하면, 그 이전 호출자인 tsp(j, ...)가 dp[j][...] 값을 갱신( Math.min )하고 저장합니다.
9. 최종 반환: 모든 재귀가 복귀하며 dp 테이블이 채워지고, 최종적으로 dp[0][1]의 값이 반환됩니다. (dp[0][1] : 이 문제가 요구하는 답인, 시작점에서부터 남은 도시를 다 순회한 후 다시 돌아오는 최단 경로)

5. (막힌 부분) Infinity 초기화 문제

처음에 탑다운 DP로 접근했을 때, 시간 초과가 발생하는 문제가 있었습니다. 해결의 근거를 백준 질문 게시판에서 발견할 수 있었는데, 이는 처음 dp 배열을 초기화할 때 편의상 Infinity로 값을 모두 넣어둔 것이 화근이었습니다.

처음부터 Infinity를 넣어두면, 해당 도시를 방문하지 않은 상태인건지, 방문을 해봤지만 더이상 유효한 경로가 없는 상태인건지 분간을 할 수 없어서 메모이제이션을 실패하게 되는 시나리오가 발생합니다.

1. tsp(A, vis)가 호출되어 dp[A][vis]를 계산합니다.
2. A에서 갈 수 있는 유효 경로가 없어 dp[A][vis]에 Infinity가 저장됩니다.
3. 나중에 tsp(A, vis)가 또 호출됩니다.
4. if (dp[A][vis] !== Infinity)는 false가 됩니다. ( Infinity !== Infinity -> false )
5. 메모이제이션이 실패하고, “길이 없음”을 알기 위해 또다시 $N$번의 for 루프를 도는 중복 계산이 발생합니다.

따라서 올바른 해결은 ‘계산 안 한 상태’와 ‘계산 결과가 Infinity인 상태’를 구분해야 하고, 그러면 아래와 같이 메모이제이션이 동작합니다.

1. dp 배열을 -1 (Sentinel 값)로 초기화합니다. (이 문제의 경우 0으로 지정해도 무관합니다.)
2. 메모이제이션 확인: if (dp[curr][vis] !== -1)
3. tsp 함수 진입 시 dp[curr][vis] = Infinity;를 먼저 넣어두고 계산을 시작합니다. 경로를 탐색하며 더 적은 비용이 해당 dp값에 점차 갱신되게 됩니다.
4. for 루프가 끝나면 dp[curr][vis]는 유효한 최소 비용이거나, 경로가 없었다면 Infinity로 남아있게 됩니다.

6. 정리

DP와 비트마스크와 같은 최적화 알고리즘을 연습해볼 수 있는 문제였습니다. 오랫동안 연구되어온 문제인 만큼 이 문제에 대해서만 정말 다양한 방법이 있습니다. 최적화된 방법을 떠올려내는 것이 어렵지만, 그만큼 많은 통찰을 얻을 수 있는 재밌는 문제입니다.