[백준_10971] 외판원 순회2 ( 브루트포스 - 완전탐색 )

문제

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

10971번: 외판원 순회 2

 

How to Solve ?

 

1) 문제를 이해했는가?

 

외판원은 여행을 할 때, 주어진 도시를 모두 거쳐야 하며, 도시를 중복하여 갈 수 없다. ( 단, 다시 돌아가는 것을 허용 )

 

나는 외판원 문제를  위의 내용과 같이 이해를 했었는데, 그 말이 무슨 뜻이냐면 아래와 같이 거쳐서 갈 수 있는 모든 경우의 수를 찾고, 다시 돌아가는 경우 중 가장 작은 값을 뽑는 문제 인 줄  알았다.

 

즉 <  0 -> 1 -> 2 -> 3 -> 2- > 1 -> 0 > 을 순회 해야 한다고 가정하고 문제를 풀었는데

 

문제에서는 < 0 -> 1 -> 2 -> 3 -> 0 > 으로 갔을 때의 최소한의 비용을 구하라는 것 이였다.

 

[
  '0123', '0132', '0213',
  '0231', '0312', '0321',
  '1023', '1032', '1203',
  '1230', '1302', '1320',
  '2013', '2031', '2103',
  '2130', '2301', '2310',
  '3012', '3021', '3102',
  '3120', '3201', '3210'
]

 

2) 어떻게 풀지 ?

 

[1] 모든 도시의 이동순서 만들기

 

외판원은 결과적으로 모든 도시를 거쳐야 하기 때문에 비용이 달라 질 수 있는 경우는 <도시의 이동 순서>를 변경 하는 것이다.

모든 경우의 수를 봐야 최소의 경우를 알 수 있기에, < 이동 순서 > 는 곧 순열(중복X, 순서O) 이기에,  백트래킹을 이용하여 구할 수 있었다.

// solve 함수에서 호출한 경우라 < output, permu_arr, visited > 가 인자로 있지만
// 전역 변수로 선언 되었다면 위의 값들을 넘겨 줄 필요는 없다.
function getPermutation(cnt, output, permu_arr, visited) {
  if (cnt === n) {
    permu_arr.push(output.join(""));
    return;
  }

  for (let i = 0; i < n; i++) {
    if (visited[i] === 1) continue;
    visited[i] = 1;
    output.push(i);
    getPermutation(cnt + 1, output, permu_arr, visited);
    output.pop();
    visited[i] = 0;
  }
}

 

[2] 이동 순서에 따른 비용 계산

 

필자는 이 부분에서 시간을 꽤 잡아 먹었는데, 예를 들어 설명 함으로써 이해를 돕고자 한다.

 

예시 : 이동순서가 <0,1,2,3> 인 경우

 

이동 순서가 <0,1,2,3> 인 경우는 결과적으로 Map[0][1] + map[1][2] + map[2][3] + map[3][0] 이다.

고로 루프를 1에서 N보다 작은 값까지 순회하면서

 

sum += map[cur_map[j-1][cur_map[j]]  를 해준 뒤 마지막에 다시 돌아가기 위한 값이 map[cur_map[n-1][0] 을 더하면 된다.

 

function solution(n, map) {
  let answer = Infinity;
  const output = [];
  const permu_arr = [];
  const visited = Array(n + 1).fill(0);

  getPermutation(0, output, permu_arr, visited);

  for (let i = 0; i < permu_arr.length - 1; i++) {
    let sum = 0;
    let cur_map = permu_arr[i].split("").map((e) => +e);

    for (let j = 1; j < n; j++) {
    // 갈 수 없는 도시가 있으면 => break;
      if (
        map[cur_map[j - 1]][cur_map[j]] === 0 ||
        map[cur_map[j]][cur_map[j - 1]] === 0
      ) {
        answer = Infinity;
        break;
      }
	// [0][1] + [1][2] + [2][3]
      sum += map[cur_map[j - 1]][cur_map[j]];
    }
	// [3][0]
    sum += map[cur_map[n - 1]][cur_map[0]];
    answer > sum ? (answer = sum) : answer;
  }

  return answer;
}

 

전체 코드

function getPermutation(cnt, output, permu_arr, visited) {
  if (cnt === n) {
    permu_arr.push(output.join(""));
    return;
  }

  for (let i = 0; i < n; i++) {
    if (visited[i] === 1) continue;
    visited[i] = 1;
    output.push(i);
    getPermutation(cnt + 1, output, permu_arr, visited);
    output.pop();
    visited[i] = 0;
  }
}

function solution(n, map) {
  let answer = Infinity;
  const output = [];
  const permu_arr = [];
  const visited = Array(n + 1).fill(0);

  getPermutation(0, output, permu_arr, visited);

  for (let i = 0; i < permu_arr.length - 1; i++) {
    let sum = 0;
    let cur_map = permu_arr[i].split("").map((e) => +e);

    for (let j = 1; j < n; j++) {
      if (
        map[cur_map[j - 1]][cur_map[j]] === 0 ||
        map[cur_map[j]][cur_map[j - 1]] === 0
      ) {
        answer = Infinity;
        break;
      }

      sum += map[cur_map[j - 1]][cur_map[j]];
    }

    sum += map[cur_map[n - 1]][cur_map[0]];
    answer > sum ? (answer = sum) : answer;
  }

  return answer;
}

const n = 4;

const map = [
  [0, 10, 15, 20],
  [5, 0, 9, 10],
  [6, 13, 0, 12],
  [8, 8, 9, 0],
];

console.log(solution(n, map));