[백준]10971번 '외판원 순회2' 문제 풀이 - JavaScript

[백준]10971번 '외판원 순회2' 문제 풀이 (JavaScript,nodejs)

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력 1

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

예제 출력 1

35

👉 풀이 코드

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

const n = Number(input[0]);
const graph = input.slice(1).map((line) => line.split(' ').map(Number));
const visited = new Array(n).fill(false);
let min = 1e9;

function dfs(depth, start, cost) {
  if (depth === n - 1 && graph[start][0] !== 0) {
    min = Math.min(min, cost + graph[start][0]);
    return;
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i] && graph[start][i] !== 0) {
      visited[i] = true;
      dfs(depth + 1, i, cost + graph[start][i]);
      visited[i] = false;
    }
  }
}

visited[0] = true;
dfs(0, 0, 0);

console.log(min);

👉 풀이 해설

본 문제는 각 탐색마다 가장 작은 비용을 선택하는 모든 경우의 수를 고르는 브루트포스, 백트래킹 알고리즘으로 문제를 풀 수 있다.

1. 먼저 입출력을 받아서 n과 graph 배열 변수에 담아주었다.
2. 한번 방문한 도시는 재방문할 수 없기 때문에 방문한 도시는 방문 했다고 체크하기 위해서 visited라는 배열 변수를 n길이만큼 false로 초기화해주었다.
3. 최소 비용을 담기 위한 배열 min 변수를 최댓값으로 초기화해주었다.

어느 도시에서 출발을 하던지 모든 경우의 수를 탐색했을 때 총 이동 비용은 결국 같기 때문에 각 도시 간에 출발 점을 첫 번째 도시를 출발점으로 잡았다.

즉, graph배열의 0번째 인덱스부터 출발을 하도록 해서 처음 dfs를 호출하기 전에 visted에 0번째 인덱스를 true로 주어서 시작을 알렸다.

반응형

dfs에는 3개의 매개변수가 있다.

1. n만큼 도시를 순회하기 위한(depth)
2. 현재 도시에서 다음 도시를 이동할 인덱스(start)
3. 이동하면서 드는 비용(cost)

dfs함수에서 중단점이 제일 중요한데, 중단점은 결국 순회에 다 달았을 때 어떤 결과 값을 가질 것인지를 결정하는 곳이다.

첫 번째 도시에서 시작하고 결국 항상 첫번째 도시로 다시 돌아와야 한다.

depth가 n-1만큼 될 때 중단 해주도록 하고 이 중단점에서 첫 번째로 돌아올 때 비용을 더해주면 된다.

그리고 처음 dfs를 호출했을 때 바로 이 중단점으로 들어가면 안 되기 때문에 graph[start][0] 값이 0이 아닐 때 중단이 될 수 있도록 해주었다.

결과적으로 이 중단점에서는 최소 비용을 구해야 한다.

현재까지 구한 최소 비용 min과 현재까지 재귀를 돌면서 구한 비용 cost + 첫 번째로 다시 돌아갈 때의 비용을 비교해서 더 작은 값을 min 변수에 담아주도록 한다.

 

아직 중단될 조건이 되지 않는 다면 for문으로 가게 되는데,

여기서는 아직 방문하지 않았거나 다음 도시로 이동할 수 있으면(비용이 0이 아니면) 현재 인덱스를 방문처리 해주고 dfs함수에 depth를 1 증가시켜 주고 우리가 다음 가야 할 도시

즉, 현재 인덱스를 start로 주고, 이동할 때 드는 비용을 더해서 재귀함수를 호출해 준다.

수행이 끝나면 방문 처리를 해제해주도록 했다.

 

마지막으로 지금까지 최솟값을 구한 min을 출력해 줌으로써 해결해 줄 수 있다.