백준 10971번: 외판원 순회 2 - javascript

3 분 소요

백준 10971번: 외판원 순회 2

문제 설명

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

출력

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

접근

출력
35

입력은 표로 보면 이렇게 된다.

도시	0	1	2	3
0	0	10	15	20
1	5	0	9	10
2	6	13	0	12
3	8	8	9	0

각자 자기자신까지의 비용은 0이며 모든 경로는 순회가능하다.
이떄 비용은 대칭적이지 않다.
그리고 모든 도시를 한 번 만 거치면서 시작점으로 돌아와야 된다.
그리고 경로 값이 0인 경우는 갈 수 없다.

이 4가지 조건을 가지고 풀어야한다.

처음에는 되게 간단하게 생각했었다.
약간 brute force 문제라고 너무 시간을 사용하려 했던 것이 문제였다.
나는 기존에 모든 수열을 만드는 코드를 짜고 있었기 때문에 다음과 같이 진행했다.

모든 수열을 만든다.
해당 순서대로 경로값을 대입하고 마지막에 제일 뒤와 제일 앞의 경로만큼의 값을 추가로 더한다.
2.1 만약 경로 중에 0인 값이 있으면 바로 해당 덧셈은 종료한다.

이런식으로 풀었는데…
정답은 나왔지만 제출해보니 시간초과가 나왔다.
생각해보니 그럴만도 한게, 위의 방식대로하면 먼저 N개의 도시의 모든 수열은 N! 만큼 계산해야한다.
그리고 그에 대한 경로 계산은 NxN 만큼 돌아간다.
N! 만큼 해도 모자를 판에 NxNxN! 만큼 돌렸으니 당연히 시간초과가 뜰 수 밖에…

그래서 기존의 식을 이리저리 고치다가 결국 검색을 했는데…
나는 왜 저런 아이디어를 생각하지 못하나 싶을 정도의 간단하고 좋은 아이디어가 있더라.

기존의 수열을 만드는 부분에서 경로값이 0이 아니면서 중복이 아닐때만 재귀를 한다.
그런데 우리는 맨처음 도시로 다시 돌아와야 된다.
나는 이 부분을 재귀함수에 매개변수로 first 등을 넣어서 기본값은 -1로 넘겨주어서 first가 있는지 없는지 판별하고 막 돌리려고했다….
그러자 코드가 복잡해져서 경로계산의 순서가 바뀌는 사태가 터졌는데, 이걸 내가 검색하신 분은 그냥 맨처음에 N만큼 반복문을 돌려서 재귀함수에 첫번째 값 start를 바로 매개변수로 넘겨주시더라!… 아!… 너무 재귀에 미쳐서 모든 것을 매개변수로 넘기려 했던 탓이다.

생각해보니 예전에 어떤 강의에서 함수를 짤 때 되도록이면 함수는 한가지의 역할만 하도록 짜라고 하셨었는데… 여전히 나는 그 가르침을 100% 실행하지 못한다는 것을 매번 느낀다.

다시 문제로 돌아와서, 결국 나는 초기실행 반복문 함수 하나와 재귀 반복문 이렇게 2개로 나눠서 시간복잡도를 N!으로 줄이는데 성공했다.
방법은 다음과 같다.

i=0부터 n-1까지 반복문을 돌리면서 재귀함수에 (깊이 카운터, N값, 시작i값, next용 i값, sum값) 을 넣어준다.
재귀함수는 현재 깊이가 N만큼 들어왔는지, 그리고 next값이 맨처음 시작i값이랑 같은지 판별한다. 2.1 만약 같으면 전역변수 min에 현재 min과 지금까지 이어온 sum값을 비교해서 작은 값을 넣고 함수를 반환한다.
2번조건이 부합하지 않으면 0부터 n-1까지의 반복문으로 넘어간다.
만약 중복체크 배열의 i값이 false고 경로배열의 (next,i) 값이 0이상이면,
해당 중복체크 배열의 i값을 true로 바꿔주고,
재귀 함수에 (깊이카운터+1, N값, 시작i값, next용 현재 i값, sum+경로[next,i]값) 을 넘겨준다. 4.1 넘겨준뒤 중복체크 배열의 i값은 false로 바꿔준다.
재귀가 종료되면 전역변수 min에는 최적의 경로값이 저장되있으므로 출력해준다.

말로 표현하려니 뭔가 어려운데, 결국은 N과 M 시리즈의 변형같은 문제다.
모든 수열을 구하는 과정에서 다른 연산을 하는 것 뿐이다.
~~간단하다~이래놓고 이번 문제 3시간넘게 잡고 있었다~~

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let city = [];
let min = 987654321;
let check = new Array(10).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;  
  let n = input.splice(0,1);
  //입력 받은 도시문자열 배열화
  input.reduce((acc,cur)=>{
    city.push(cur.split(' '));
  },'')
  
  tsp(n);  
  console.log(min);
  process.exit();
});

//시작 노드값을 따로 지정하지 않기 위한 시작용 반복문
let tsp = function(n){
  for(let i=0;i<n;i++){
    re(0,n,i,i,0);  
  }  
}

//무한정 경로값을 합하는 재귀
let re = function(cnt,n,start,next, sum){
  //재귀 중 시작으로 돌아옴을 판별하는 브레이크 조건
  if(cnt==n&&start==next){    
    min = Math.min(min,sum);
    return;
  }
  //모든 경우의 수열 반복문
  for(let i=0;i<n;i++){
    //방문 한 적이 없고 해당 경로 값이 0이상일때
    if(!check[i]&&city[next][i]*1>0){   
      check[i] = true;
      if(sum + city[next][i]*1 < min){
        re(cnt+1,n,start,i,sum+city[next][i]*1)
      }
      check[i] = false;
    }
  }
}

Twitter Facebook LinkedIn

ryeon

백준 10971번: 외판원 순회 2 - javascript