[백준 10971] 외판원 순회2

 

외판원 순회는 풀 수 있는 방법이 많다

하지만 N값이 커지면, 도시의 개수가 많아지면 브루트포스와 백트래킹

그러니까 완전탐색 방식으로는 시간초과가 뜬다

 

따라서 N값이 커지면 dp랑 비트마스크를 써야하는데

(사실 비트마스크는 필수가 아니다)

 

이 문제는 N값이 작으므로 백트래킹으로 해도 충분히 해결되었다

 

그냥 dfs 코드를 개조해주면 된다

 

주의할 점은

만약 배열의 원소값이 0이면 이건 길이 없는거라 예외처리를 해줘야한다

즉 if문에 길이 있을때 조건을 추가해야함

 

모든 정점을 다 방문했으면 그때서야 전역변수인 MIN을 건들 수 있게 된다

 

---

#include <iostream>
#include <limits.h>
#define SIZE 11

using namespace std;

int arr[SIZE][SIZE];
bool visited[SIZE];
int MIN;
int N;

bool check() {
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) return false;
	}
	return true;
}

void DFS(int sum,int start) {

	if (check()) {
		if (arr[start][1]>0 && sum+arr[start][1] < MIN) {
			MIN = sum + arr[start][1];
		}
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i] && arr[start][i]>0) {
			visited[i] = true;
			DFS(sum+arr[start][i],i);
			visited[i] = false;
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	MIN = INT_MAX;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cin >> arr[i][k];
		}
	}

	visited[1] = true;
	DFS(0, 1);
	cout << MIN;
	return 0;
}