[백준]Baekjoon10971(순열)

문제링크 : https://www.acmicpc.net/problem/10971

풀이

외판원이 순회할 수 있는 경로를 모두 검사하면서 그 중 가장 최솟값을 구하면 문제를 풀 수 있다.

순회 경로같은 경우 만약 N=4라면 배열에 0 1 2 3 을 넣어놓은 후

next_permutation함수를 통해 구해주었고

순열이 바뀔 때마다 경로비용의 합을 구해주면서 최솟값을 추출하도록 하였다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10][10];
int permutation[10];
int main()
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	for (int i = 0; i < N; i++) permutation[i] = i;

	int minimum = 10000000;
	do {
		int result = 0;
		bool b = true;
		for (int i = 0; i < N; i++) {
			if (i == N - 1) {
				if (arr[permutation[i]][permutation[0]] == 0) {
					b = false; break;
				}
				else
					result += arr[permutation[i]][permutation[0]];
			}
			else {
				if (arr[permutation[i]][permutation[i + 1]] == 0) {
					b = false; break;
				}
				else result += arr[permutation[i]][permutation[i + 1]];
			}
		}
		if (result < minimum && b == true) minimum = result;
	} while (next_permutation(permutation,permutation+N));

	printf("%d\n", minimum);
}