외판원 순환 문제 알아보기

• 몇 달 내려놓았던 알고리즘을 다시 풀고자 문제를 찾아보던 중 처음 보는 문제를 접하게 되었다.
• 외판원 순환 문제라는 것인데, 문제를 풀고 이해한 것을 남겨보고자 한다.

---

외판원 순환 문제(Traveling Salesman Problem - TSP)란?

  여러 도시와 도시 사이의 이동 비용이 주어질 때, 어느 한 도시에서 시작하여 모든 도시를 순회한 후 처음 시작점이 되는 도시로 돌아올 때까지 걸리는 최소 비용을 구하는 문제이다.

 

외판원 문제 - 위키백과, 우리 모두의 백과사전

 

 

해결 방법에 대한 고민

  처음 문제를 딱 봤을 때 떠오른 점을 나열하자면 아래와 같다.

• 도시와 도시 사이의 이동 비용이 주어진다.
  • 도시가 노드, 도시 사이의 이동 비용이 가중치로 주어진 그래프 문제이다(방향 가중치 그래프)
• 처음 시작점이 되는 도시에서 모든 도시를 순회한 후, 처음이 되는 도시로 다시 돌아와야 한다.
  • 즉 '사이클'을 의미한다.
  • 따라서 문제에서 달리 시작점을 정하지 않았으나, 어차피 모든 점을 다 방문하는 사이클을 찾아야 하기 때문에 시작점을 무엇으로 정하던지 상관없다.
  • 이 점을 이용하여 문제 풀이에선 무조건 1번 도시를 시작점으로 삼아 풀이한다.

 

  여기까지는 생각이 깔끔하게 정리되었는데, 그 다음이 문제였다.

• 최단 경로를 구해야하기 때문에, DP 형식으로 특정 노드에서 다른 노드까지의 최단경로를 기록한다.
  • 문제는, 이렇게만 하면 기록한 최단경로 사이에 어떤 노드들을 지나쳐왔는지 알 수 없으므로 '모든 도시를 순회해아 한다'라는 조건에 부합차지 않게 된다.
  • 이 부분을 어떻게 해결할까 고민하다, 서치를 통해 찾은 방안이 'arr 속 모든 노드를 지난 상태에서 i번 노드를 거쳐 다시 시작노드로 돌아오는 최소 경로'를 기록하는 방안이었다.
  • 이 때 지나쳐온 경로는 비트 마스킹으로 표현한다.

 

비트 마스킹은 간단하게 데이터를 이진법으로 표현하여 처리하는 것을 의미한다. 알고리즘 문제 풀이에서는 집합/배열 등을 빠르고 쉽게 처리하기 위한 용도로 쓰인다. 이 부분의 구현 등은 나중에 더 정리해보기로!

 

 

  원리는 이러하다. 위에서 정한 대로 1번 노드를 시작점으로 고정시킨다고 가정하면, 구해야 하는 최소 경로의 가짓 수는 아래와 같이 나타낼 수 있다.

// a노드에서 b노드 까지의 가중치를 cost[a][b]라고 가정한다

[1번 노드에서 시작하여 나머지 노드를 순회하여 돌아오는 최단경로]
= [i번 노드에서 시작하여 나머지 노드를 순회하여 돌아오는 최단경로] + cost[i][1];

 

• 1번 노드에서 시작하여 나머지 노드를 순회하고 돌아오는 최단경로는, (1번을 제외한 나머지 부분집합의 노드들에서 하나를 골라 출발하여 모든 노드를 순회하고 다시 돌아오는 경로 + 부분집합의 시작점에서 1번으로 가는 가중치) 라고 정리할 수 있다.
• 위와 같은 방식으로 최단경로를 작게 쪼개나가며 Bottom-up 방식으로 구현할 수 있다.

 

문제 풀이 - 백준 10971번 외판원 순회 2

  이 주제를 접할 수 있게 한 문제. 태그를 보아하니 지나온 노드를 체크하며 완전 탐색 형식으로 푸는 방법도 유효한 것으로 보이는데, N의 조건이 커지면 커질수록 통과하기 어려운 코드가 될 것 같았기에 추후의 심화 문제 풀이를 위해 위에서 살펴본 방식을 활용하기로 하였다.

 

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

let input = [];

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  const [N] = input.shift();
  const maxNum = 1 << N; // 방문 여부를 비트마스킹으로 표현하기 위함
  const dpArr = Array.from(Array(N + 1), () => Array(maxNum).fill(-1));

  // visited 내 노드들을 지난 후 current에서 시작점까지의 최소 경로를 반환한다
  // visited => 비트마스킹 방식으로 표현된 방문 노드 목록
  
  const search = (current, visited) => {
    // 모든 노드를 방문했을 경우
    if (visited === (maxNum - 1)) {
      if (input[current][0] === 0) return Infinity;
      
      // 모든 노드를 방문했다면 남은 것은 현재 위치(current)에서 시작점으로 돌아가는 것이므로,
      // 해당 경로의 가중치를 반환한다
      else return input[current][0];
    }
    // 이미 계산된 값은 그대로 반환
    if (dpArr[current][visited] !== -1) return dpArr[current][visited];

     
    // 아직 계산되지 않았다면, 최소경로 계산을 위해 값을 Infinity로 초기화한다
    dpArr[current][visited] = Infinity;

  	// 1번부터 N번 노드 전체에 대해 경로를 탐색한다
    for (let i = 0; i < N; i++) {
      // 이미 방문한 점이거나, 현재 노드에서 i번 노드로 가는 길이 없으면 계산하지 않는다
      if (input[current][i] === 0 || visited & (1 << i)) {
        continue;
      }

	  // current에서 갈 수 있는 모든 노드로 진행했을 때의 최소 경로를 계산한 후, 최소값을 반영한다
      dpArr[current][visited] = Math.min(dpArr[current][visited], search(i, visited | (1 << i)) + input[current][i]);
    }
    return dpArr[current][visited];
  };

  // 1(0)번 노드에서 시작.
  const answer = search(0, 1);
  console.log(answer);

  process.exit();
});

 

---

• 아주 기초적인 아이디어는 생각해냈지만 디테일을 떠올리지 못해 애먹은 문제였다.
• 특히 비트마스킹은 블로그에서 언급하진 않았지만 몇 번 접한 적은 있는 기법인데, 아직 필요할 때 바로바로 머리 속에서 튀어나오지 않는 걸 보아하니 다양한 문제 풀이가 필요할 것 같다.