BOJ - 10971 외판원 순회 2

1. 문제 링크 : https://www.acmicpc.net/problem/10971

2. 문제 유형 : 백트래킹

3. 문제 티어 : 실버2

4. 문제 풀이
 : 전형적인 모든 경우의 수를 완전 탐색하는 백트래킹 문제
 : 모든 도시를 방문 후 다시 돌아와서 그 최소 경로를 구해야  함
 : 이 과정에서 방문 처리 유무를 남겨놓아서 다시 방문하지 않도록 하여 연산 속도 빠르게 처리

 : 도시 i부터 j까지 가서 그 비용을 현재 측정된 비용에 더한 후 기존에 있던 최솟값과 지속적으로 비교해서 최솟값을 갱신하는 재귀함수 호출하면서 최적의 값 찾음

 

5. 문제 코드 

// 1. 값 입력 받기
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let W = []; // 비용 행렬

// 2. 방문 여부와 최솟값 변수 선언
let visited = Array(N).fill(false);
let minValue = Infinity; // 초기에 제일 큰 수로 잡아두고 비교하면서 점점 내려옴
let startCity = 0;

// 3. 비용 행렬 입력 받기
for(let i = 0; i < N; i++) {
   W[i] = input[i+1].split(" ").map(Number);
}

// 4. 재귀 함수 호출
// 현재 방문한 도시, 방문 횟수, 방문 비용을 통해 재귀함수
function tsp(currentCity, count , cost) {
   if(count === N) { // 이미 모든 도시를 방문한 경우
       if(W[currentCity][startCity] > 0) { // 출발지로 돌아가는 경로가 있는 경우
          minValue = Math.min(minValue , cost + W[currentCity][startCity]); // 현재까지 총 비용인 cost에 현지 시점 비용 더함
          }
          return;
     }
     for(let nextCity = 0; nextCity < N; nextCity++) {
         if(!visited[nextCity] && W[currentCity][nextCity] > 0 ) { // 방문하지 않았고 다음 도시로 가는 경로가 있는 경우
             visited[nextCity] = true; // 방문 처리
             tsp(currentCity, count + 1, cost + W[currentCity][nextCity]);
             visited[nextCity] = false; // 다시 방문 처리 초기화
          }
     }
}

visited[startCity] = true; // 시작 도시 방문 처리
tsp(startCity, 1, 0); 
console.log(minValue);

 

6. 시간복잡도 

: 도시 방문 순서를 모든 순열로 확인해야하므로 O(N!)