[백준 10971] 외판원 순회 2 C++

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

외판원순회 2

문제풀이

 

W[i][j]는 i -> j로 가는 비용을 말합니다. 만약 1, 2, 3 의 도시가 있다면 모든 도시를 모든 방법으로 방문해보면 됩니다. 

이 문제는 W[i][i] i,i 즉 자기 자신은 0입니다. 그리고 W[i][j] i -> j로 가는 방법 중에 경로가 없으면 0으로 표시합니다.

이 문제는 경로가 없을 때를 꼭 고려해주어야지만 정답을 맞출 수 있습니다. 따라서 W[i][j] 를 탐색할 때 0을 발견할 땐 경로 계산을 해주지 말아야 합니다.

 

저는 이 문제를 다음과 같이 풀었습니다.

만약 3이라는 수가 들어온다면 갈 수 있는 경로는 (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2,), (3, 2, 1) 각 자리가 중복되지 않는 모든 경우의 수를 구해보면 됩니다.

모든 순열 구하기의 문제와 같이 코드를 작성한 후, 

 

각 각의 인덱스 값을 계산하도록 했습니다. N이 만약에 3이인데 1->2, 2->3, 3->1로 다시 돌아와야 합니다. 

여기서는 1, 2, 3으로 표시했지만, 코드상은 0, 1, 2로 표시했기 때문에 % N을 함으로써 다시 첫번째로 돌아오게끔 만들었습니다.

 

따라서 N이 3일 때, (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)순으로 값을을 참조하여 계산했습니다.

 

만약 0 -> 1로 가는 경우의 수인데 0을 발견했다면 sum에다가 아주 큰값을 넣어서 최소값을 안구하면 됩니다. 

int temp = input[selected[i] - 1][selected[index] - 1]; 에서 -1을 한 이유는 1 ,2, 3이 아니라 0, 1, 2을 구하기 위함입니다. 

#include <iostream>
#include <algorithm>
using namespace std;

#define input_max 10 + 1


int min_val = 1e9;
int selected[input_max];
int origin_num[input_max];
int input[input_max][input_max];
bool check[input_max];
int result;
int n;

void init() {

	for (int i = 0; i < 10; i++) {
		origin_num[i] = i + 1;
	}
}

void cal_tsp() {
	int sum = 0;
	for (int i = 0; i < n; i++) {

		int index = (i + 1) % n;
		
		int temp = input[selected[i] - 1][selected[index] - 1];

		if (temp == 0) {
			sum = 1e9; // 0을 갈 수 없는 길이니 최댓값을 넣으면 됩니다.
			break;
		}
		sum += input[selected[i]-1][selected[index]-1]; // -1을 하여 인덱스 번호에 접근합니다
	}

	

	min_val = min(min_val, sum);
}

void go(int depth) {

	if (depth == n) {

		cal_tsp();
		return;
	}

	for (int i = 0; i < n; i++) {

		if (check[i]) continue;

		check[i] = true;
		selected[depth] = origin_num[i];
		go(depth + 1);

		check[i] = false;
		
	}
}
void solution() {

	init();

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> input[i][j];

			
		}

	

	go(0);
	result = max_val;
	cout << result << '\n';
	
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solution();


	return 0;
}