[BOJ] 외판원 순회2

[10971] 외판원 순회2

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

• 영어로 Travelling Sales Problem (TSP)
• 1번 부터 N번까지 번호가 매겨져있는 도시가 있다.
• 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다. (한 번 갔던 도시로는 다시 갈 수 없다.)
• 이때, 가장 적은 비용을 구하는 문제
• W[i][j] : i -> j 비용

 

 

Solution

• 0~N-1 까지 담고 있는 a[] 배열을 사용해 다음 순열을 구한다.
• W[i][j] 배열의 비용을 a[] 배열의 바뀌는 순서에 맞게 더해 최소 비용을 구한다.

 

 

소스코드

import java.util.Scanner;

public class Main {
	int[][] w;

	public void go() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		w = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				w[i][j] = sc.nextInt();
			}
		}

		for (int i = 0; i < n; i++) {
			a[i] = i;
		}

		int min = Integer.MAX_VALUE;
		loop: do {
			int cost = 0;
			for (int i = 0; i < n - 1; i++) {
				if (w[a[i]][a[i + 1]] == 0) {
					continue loop;
				}
				cost += w[a[i]][a[i + 1]];
			}
			if (w[a[n - 1]][a[0]] == 0)
				continue loop;
			else
				cost += w[a[n - 1]][a[0]];
			min = Math.min(min, cost);
		} while (next_permutation(a, n));
		System.out.println(min);
	}

	public boolean next_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j]) {
			j -= 1;
		}
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}