백준 10971번 외판원 순회 2 (C++)

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

10971번: 외판원 순회 2

문제자체는 흔한 백 트래킹 문제이다.

로직 자체는 어렵지 않으나, 유의해야할 점이 2가지 있다.

 

1. 최대값 선정 

각 행렬의 성분은 최다 1,000,000 이고 최대 도시의 갯수는 10개이다. 

만약 최대값을 1e4로 선정한다면 오답을 겪을 수 있다. 고로 최대값을 1e9으로 선정해주자.

 

2. 갈 수 없는 길은 '0'으로 표시한다 && 마지막 마을에서 출발 마을로 되돌아와야 한다.

	if(cnt==n){
		if(v[index][start]==0) return; // 중요
		if(ans>sum+v[index][start]) ans = sum+v[index][start];
		return;
	}

이 부분은 n개의 마을만큼 순회했을때, 최대값과 비교하여 정답을 저장하는 과정이다. 

이때 중요한게 두 번째 줄인데, 우리는 마지막 마을에서 출발 마을로 되돌아와야 한다. 

만약 마지막 마을에서 출발 마을로 되돌아 올 수 없다면(=0), 이 루트는 사용할 수 없는 루트이다.

저 중요표시 된 부분을 적어주지 않는다면 오답이 나오게 된다.

 

#include <iostream>
using namespace std;

bool ch[11] = {false,};
int n = 0, ans = 1e9;
int v[10][10];

void go(int start, int index, int cnt, int sum){
	if(cnt==n){
		if(v[index][start]==0) return; // 중요
		if(ans>sum+v[index][start]) ans = sum+v[index][start];
		return;
	}
	for(int i=0; i<n; i++){
		if(ch[i]||v[index][i]==0) continue;
		ch[i] = true;
		go(start,i,cnt+1,sum+v[index][i]);
		ch[i] = false;
	}
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> v[i][j];
		}
	}
	for(int i=0; i<n; i++){
		ch[i] = true;
		go(i,i,1,0); // 최초 출발지점, 현재 위치, 지나간 마을수, 이동비용
		ch[i] = false;
	}
	cout << ans << "\n";
	return 0;
}