Node.js)백준 10971번: 외판원 순회 2

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

10971번: 외판원 순회 2

 

 

전체 코드

const [ n, ...nums ] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n')
const N = +n
const board = nums.map(v=>v.split(' ').map(Number))
let min = 10000000;

for(let i = 0; i<N; i++){
  let res = salesman(i,i,1<<i,0);
  if (min > res) min = res;
}

console.log(min)

function salesman(start,pos,visited,dist){
  if(visited == (1<<N)-1){
    if(board[pos][start]!=0){
      dist +=board[pos][start]
      if(dist<min) min = dist
    }
    return;
  }
  for(let next = 0; next<N; next++){
    if(!(visited & (1<<next)) && board[pos][next] != 0 && min>dist+board[pos][next]){
      salesman(start,next,visited|(1<<next),dist+board[pos][next]);
    }
  }
}

 

---

for(let i = 0; i<N; i++){
  salesman(i,i,1<<i,0);
}

salesman(시작 도시, 현재 방문 도시, 방문한 도시, 순회 거리) 

 

시작 도시:  원래의 도시로 돌아오는 순회 여행 경로를 찾는 문제이기 때문에 시작 도시로 돌아와야한다. 따라서 시작 도시를 기억하고 있어야한다. 

 

현재 방문 도시: 현재 방문한 도시를 기억하고, 그 도시에서 갈 수 있는 도시를 탐색한다. 

 

방문한 도시: 방문한 도시는 1, 아직 방문하지 않은 도시는 0으로 놓고 비트연산을 통해 방문가능한 도시인지 체크한다. 

 

순회 거리 : 외판원이 이동한 총 거리를 나타낸다. 

---

for(let next = 0; next<N; next++){
    if(!(visited & (1<<next)) && board[pos][next] != 0 && min>dist+board[pos][next]){
      salesman(start,next,visited|(1<<next),dist+board[pos][next]);
    }
  }

 아직 방문하지 않았고, 방문할 수 있고, 그 지점을 방문했을 때 거리가, 현재 최소거리 보다 작다면 그 지점을 방문한다. 

 

---

 if(visited == (1<<N)-1){
    if(board[pos][start]!=0){
      dist +=board[pos][start]
      if(dist<min) min = dist
    }
    return;
  }

 

모든 도시를 방문하면?

마지막 도시에서 첫번째 도시로 이동할 수 있다면?

지금까지 총 순회 거리에 마지막 도시에서 첫번째 도시로 가는 거리를 더해준다.  그 거리가 현재 최소거리보다 작다면 갱신해준다.