외판원 순회 2

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 10974번 - 모든 순열 풀이 에서 알아 본 알고리즘을 이용하면 쉽게 풀 수 있습니다.
  • 완전 탐색 문제로 모든 경우의 수를 고려해서 풀 수 있습니다. 범위는 10! 로 충분히 가능한 숫자입니다.
  • 모든 경우의 수는 모든 순열을 의미합니다.
  • 순서가 중요한 문제로 모든 순열을 돌면서 각 순열마다 경로의 비용을 구합니다.
  • 그 중에서 최솟값을 구하면 정답이 됩니다.

문제 풀이 step 2

  • 이 문제는 모든 경로 중에서 갈 수 없는 경로와 갈 필요 없는 경로를 제외시켜서 속도를 향상시킬 수 있는 문제입니다.
  • 만약 w[i][j] = 0 처럼 갈 수 없는 경로일 경우에는 도중에 탐색을 중단하는 방식으로 모든 경로에서 제외시킵니다.
  • 그리고 이 문제는 한 바퀴를 돌아서 결국 다시 처음 도시로 오기 때문에 0 1 2 3, 1 2 3 0, 2 3 0 1, 3 0 1 2 모두 경로의 값이 같습니다.
  • 그렇기 때문에 시작 도시가 0 일 때만 탐색하면 되므로, 시작 도시가 0 이 아닌 경우에는 모든 경로에서 제외시킵니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

let min = Infinity;

const checkPossible = (arr, from, to) => arr[from][to] !== 0;

const calculate = (arr, route) => {
	let sum = 0;

	for (let i = 0; i < route.length - 1; i++) {
		sum += arr[route[i]][route[i + 1]];
	}
	sum += arr[route[route.length - 1]][route[0]];

	return sum;
};

// 모든 순열을 탐색하는 함수
const rec = (n, arr, visited, route, depth) => {
	// 0 1 2 3, 1 2 3 0, 2 3 0 1, 3 0 1 2 모두 값이 같다. (이유는 한 바퀴 도는 것이기 때문)
	if (depth > 0 && route[0] !== 0) return;

	// 다음 도시로 갈 수 없는 경우
	if (
		depth > 1 &&
		!checkPossible(arr, route[route.length - 2], route[route.length - 1])
	)
		return;

	if (depth === n) {
		// 마지막 도시에서 첫 도시로 갈 수 없는 경우
		if (!checkPossible(arr, route[route.length - 1], route[0])) return;

		min = Math.min(min, calculate(arr, route));
		return;
	}

	for (let i = 0; i < n; i++) {
		if (visited[i]) continue;

		visited[i] = true;
		route.push(i);
		rec(n, arr, visited, route, depth + 1);

		visited[i] = false;
		route.pop();
	}
};

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = [];
	for (let i = 1; i < n + 1; i++) {
		arr[i - 1] = input[i].split(" ").map(Number);
	}

	const route = [];
	const visited = Array(n).fill(false);
	rec(n, arr, visited, route, 0);

	return min;
};

console.log(solution(input));