외판원 순회2 - 10971

문제 :

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

10971번: 외판원 순회 2

 

소스 : 

#include <iostream>
#include <limits>
#include <algorithm>

using namespace std;

int num[10][10] = { 0 };
int arr[10] = { 0 };
int main()
{
	int n;
	cin >> n;
	//입력값
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> num[i][j];
		}
	}
	//순회할 도시 인덱스 넣기
	for (int i = 0; i < n; i++)
	{
		arr[i] = i;
	}

	int total = INT32_MAX;
	int sum = 0;
	int value = 0;
	bool check = true;
	//모든 경우의 수
	do
	{
		check = true;
		sum = 0;
		//도시 이동 비용 합
		for (int i = 0; i < n; i++)
		{
			//순회 합
			if (i < n - 1)
			{
				value = num[arr[i]][arr[i + 1]];
				if (value == 0)
				{
					check = false;
					break;
				}
				sum += value;
			}
			else // 처음으로 되돌아 오는 합
			{
				value = num[arr[n - 1]][arr[0]];
				if (value == 0)
				{
					check = false;
					break;
				}
				sum += value;
			}
		}
		if (check)
		{
			if (total > sum)
			{
				total = sum;
			}
		}
	} while (next_permutation(arr, &arr[n]));


	cout << total << "\n";

	return 0;
}

어려운 문제는 아닌데 거의 3시간 걸림....

처음엔 재귀로 시도했다가 실패..

결국 next_permutation을 사용하여 해결함.. 

오래걸린 이유

1. 문제 이해 속도 부족...

2. 구현능력 부족.. (다른 사람들 구현한거 보니 DFS로 풀 수 있는것 같음. 한번 도전해 볼것. )