[Javascript] 백준 - 외판원 순회 2

목차

1. 문제 풀이

2. 정답 코드

3. 시간 복잡도

---

1. 문제 풀이

외판원이 모든 도시를 한번씩 거쳐 마지막에 다시 출발 도시로 돌아오는 데 걸리는 최소 비용을 구하는 문제이다.

 

4개의 도시에 대하여, i -> j 로 이동할 때 걸리는 비용이 2차원 배열로 주어진다.

이 때, 기본적인 dfs 코드와는 다르게 '비용'이 있으므로, 방문할 때마다 비용을 더해줘야 한다.

또한 여러 케이스의 경로에 대하여 '총 비용'을 비교하여 최소 비용을 출력해야하므로, 모든 경로를 탐색하기 위해 백트래킹 개념을 사용하였다.

 

백트래킹은 쉽게 말하자면, 순열과 같다.

'A' , 'B', 'C', 'D' 가 있을 때, 

ABCD, ABDC, ACBD, ACDB, .... 순으로 진행되는데, 이를 구현하기 위해 

1. 한 가지 선택지를 택함
2. 그 선택을 바탕으로 다음 단계로 진행
3. 만약 진행하면서 더 이상 유효한 선택지가 없다면 (= 4 이상이라면) 되돌아가서 이전 선택지를 바꾸거나 다른 경로를 탐색한다.

 

 

그림 설명

A로 시작되는 모든 경우의 수를 구한 다음에 backtracking하여 B로 시작되는 모든 경우의 수도 구한다.

이후 C, D로 시작된느 모든 경우의 수를 쭉쭉 구하면 그게 바로 백트래킹!

---

2. 정답 코드

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

const n = Number(input[0]);
const map = input.slice(1).map((line) => line.split(" ").map(Number));

var answer = Infinity;
var visited = new Set();
var start = 0;

travel(start, 0);
console.log(answer);

function travel(cur, sum) {
  visited.add(cur);

  if (visited.size === n) {
    if (map[cur][start]) {
      answer = Math.min(sum + map[cur][start], answer); // 맨 마지막 도시에서 처음 도시로 돌아오는 경우도 계산해야함
    }
    return;
  }

  for (let next = 0; next < n; next++) {
    if (map[cur][next] && !visited.has(next)) {
      travel(next, sum + map[cur][next]);
      visited.delete(next);
    }
  }
}

 

---

3. 시간 복잡도

1) 재귀 호출 (모든 경우의 수) : O(N!)

2) 각 재귀 호출 내에서 for 문 : O(N) 

전체 시간 복잡도는 O(N!) 이다.(N! 에 비해 N은 미비한 수이므로)

---

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