백준 10971 문제. (TSP문제를 수열을 이용해 해결)

백준 문제 10971

백준 문제 10971 문제는 외판원 순회 문제로, TSP(Traveling Salesman Problem) 문제이다.

위와 같은 문제는 순열을 이용해 문제를 해결 할 수 있는데, 그 이유는 (2 <= n <= 10) 이기 때문에 최대 10! (3,628,800) 번을 검사하면 답을 찾을 수 있다. 이 정도는 순열을 이용할 수 있다고 한다.

---

문제

1번부터 N번까지 번호가 매겨져 있는데 도시들 사이에 길이 있다. 어느 한 도시에서 출발해 N 개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려 한다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외). 가장 적은 비용을 들이는 여행 계획을 구해라.

. . .

W[i][j] = 0 일 때는 도시 i 에서 j 로 갈 수 없는 경우 이다.

---

처음에 해당 문제를 어떻게 수열을 이용해 풀지? 란 생각을 할 것이다.

다음은 백준 10971 문제의 예제 입력이다.

// 처음 입력은 도시의 수 N 개
// (2 <= N 3 <= 10) 다음 N 개의 줄에는 비용 행렬
4
0  10  15  20  
5   0   9  10
6  13   0  12
8   8   9   0

이럴 때 도시의 수가 4개이기 때문에, 4! 로 나타낼 수 있다.

즉, 다음과 같이 풀어 쓸 수 있다.

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
.
.
.
4 3 2 1

즉 한 번씩 모두 돈다. 해당 문제에 적용시키면 될 것 같다.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {

	int w[20][20];

	int n = 0;
	std::cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int q = 0; q < n; ++q) {
			std::cin >> w[i][q];
		}
	}

	std::vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		a[i] = i;
	}

	int result = 999999999;

	do {
		int sum = 0;
		bool isOk = true;
		for (int i = 0; i < n - 1; ++i) {
			// 여기서 vector a 는 수열이라서 n+1 로 해도 모두 돈다.
			if (w[a[i]][a[i + 1]] == 0) {
				// [i][j] 가 0일 때 못 가기 때문
				isOk = false;
			}
			else {
				sum += w[a[i]][a[i + 1]];
			}
		}

		// 다시 출발 도시로 돌아가기
		if (isOk && w[a[n - 1]][a[0]]) {
			sum += w[a[n - 1]][a[0]];
			
			if (result > sum) {
				result = sum;
			}
		}
	} while (std::next_permutation(a.begin(), a.end()));

	std::cout << result;

	return 0;
}

잘 된다. 여기서 가장 중요한 점은 수열로 해결한단 것이다.