[완전 탐색] 백준 문제 풀이 - 10971 외판원 순회 2

👩🏻‍💻 문제링크

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

10971번: 외판원 순회 2

 

✍️ 아이디어

1. 문제 이해

• 도시 N개를 잇는 도로의 비용이 있는데 도시 N개를 모두 방문할때 최소 도로비용을 구하자

2. 순열 + 브루트포스를 이용하여 도시 N개를 방문하는 순서를 다 구함 ex) 1,2,3,4순으로 도시방문

3. 도로가 없는 경우 예외처리

if(arr[number[i]][number[i+1]] == 0) connect =false;

4. N 최댓값이 10이니까 시간복잡도 = 10 * 10!  

 

✍️소스코드

• 내 코드

#include <iostream>
#include <algorithm>
using namespace std;
int number[11]; // 방문할 도시 순서를 저장할 배열

int main()
{
	int n; cin>>n;
	int arr[n][n]; // 도로의 비용을 저장할 배열
	int min = 10000000;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			cin>>arr[i][j];
		}
	}
	for(int i=0; i<n; i++)
	{
		number[i]=i;
	}
	while(1)
	{
		bool connect = true; // 길이 끊어졌을 경우 false
		int sum = 0;
		for(int i=0; i<n-1; i++)
		{
			if(arr[number[i]][number[i+1]] == 0) connect = false; //길이 끊어진 경우
			sum += arr[number[i]][number[i+1]]; //도로 사용료의 합을 저장중..
		}
		if(arr[number[n-1]][number[0]] == 0) connect =false; //길이 끊어진 경우 예외처리
		sum += arr[number[n-1]][number[0]]; // 마지막 다시 출발점으로 복귀
		if(sum<min && connect) min=sum; // 최솟값이 생기면 갱신
		if(!next_permutation(number, number+n)) break; // 다음 도시 방문 순서 갱신
	}
	cout<<min<<"\n";
}

 

• 다른사람 코드 (N과 M 느낌으로 풀었음,  DFS) => HARD

 

체감난이도	걸린시간	참고	사용 문법
하	30min	x	완전탐색-순열