문제 풀이

플로이드 와샬 알고리즘으로 i에서 j 까지가는 최소 거리를 구해주고
n의 제한이 최대 10이므로 10! = 3,628,800 으로 완전탐색으로 풀이가 가능하다.
외판원 순회알고리즘으로 최대 16!까지 풀이가 가능하다고 하지만 잘 모르므로 추후에 공부하기로 했다.

문제 링크

boj/17182

소스코드

PS/17182.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
int arr[11][11];
int d[11][11];
int n, k;
int visit[11];
int ans = 987654321;
void solution(int cur, int cnt, int max, int val);
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> k;
	vector<pair<int, int>> v[11];
	/*for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}*/
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			d[i][j] = arr[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (d[j][k] > d[j][i] + d[i][k])
					d[j][k] = d[j][i] + d[i][k];
			}
		}
	}

	solution(k, 0, n,0);
	cout << ans;
}

void solution(int cur, int cnt, int max,int val)
{
	if (cnt == max)
	{
		ans = min(ans, val);
	}
	for (int i = 0; i < n; i++)
	{
		if (visit[i] == 1)
			continue;
		visit[i] = 1;
		solution(i, cnt + 1, max,val+d[cur][i]);
		visit[i] = 0;
	}
}