[BOJ]10971번: 외판원 순회 2(c++)

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

10971번: 외판원 순회 2

 

 

#include <iostream>
#include <algorithm>

using namespace std;

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

	const int MAX = 10;
	int min_cost = 100'000'000;

	// 입력
	int N;
	cin >> N;
	int W[MAX][MAX];
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> W[i][j];
		}
	}

	// city 인덱스 배열
	// 첫번째 도시로 다시 돌아오기 위해서 크기를 MAX + 1로 선언
	int city[MAX + 1] = { 0, };
	for (int i = 0; i < N; ++i)
	{
		city[i] = i;
	}

	// 순회가 가능한 경우, 최소 순회비용 구하기 - 완전탐색
	do {
	
		bool possible = true;
		int cost = 0;
		
		// 가장 마지막으로 갈 도시 = 첫번째 도시
		city[N] = city[0];
		for (int i = 0; i < N; ++i)
		{
			// 갈 수 없는 경우면 break
			if (W[city[i]][city[i + 1]] == 0)
			{
				possible = false;
				break;
			}

			cost += W[city[i]][city[i + 1]];
		}

		// 가능한 순회면 최소값 구하기
		if (possible && min_cost > cost)
		{
			min_cost = cost;
		}
	
		/*
			순회가 환형이므로, 시작점은 1로 고정해도 된다. 
			ex) A B C D == B C D A == C D A B == D A B C
		*/
	} while (next_permutation(city + 1, city + N));

	cout << min_cost;

	return 0;
}

 

 

문제를 구현하는 것 자체는 크게 어려운 일이 아니다.

단, 시간 조건이 충분하다면! ㅋㅋㅋ

 

외판원 순회2는 외판원 순회1 과 다르게 시간이 2초이다. 

완전탐색 연습용 문제이기 때문에 정직하게 완전탐색으로 풀었다. 

 

TIP

O(N! * N)이 아니라 O(N-1! * N)로 풀 수 있다. 

 

원래라면 N개의 수 조합 O(N!) * 비용 계산 O(N) = O(N! * N)이 걸릴테지만, 

외판원은 도시를 '환형'으로 순회한다.

 

 

어디서부터 시작해도 모두 같다. 따라서 시작점을 A로 고정해도 된다.

 

따라서 전체 시간 복잡도 / N = O(N-1! * N) 이다.

 

코드로는 아래처럼 첫번째 수 다음부터 순열을 돌리도록 하면 된다.

 while (next_permutation(city + 1, city + N));