[BOJ] 10971 - 외판원 순회 2

[백준] 10971 - 외판원 순회 2

접근

완전탐색으로 모든 경우의 수를 다 돌아보고 최솟값을 갱신하면 된당.

소스코드

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int dist[15][15], n;
bool visited[15];

int tsp(int now, int cnt) {
	// 다음 도시로 모두 탐색하고 그중 가장 짧은 경로를 선택
	if (cnt == n) {
		return dist[now][1] ? dist[now][1] : INF;
	}
	int rtn = INF;
	visited[now] = true;
	for (int i = 1; i <= n; i++) {
		if (visited[i] || !dist[now][i]) continue;
		rtn = min(rtn, dist[now][i] + tsp(i, cnt + 1));
	}
	visited[now] = false;
	return rtn;
}

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", dist[i] + j);
		}
	}

	printf("%d", tsp(1, 1));
	return 0;
}