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

안녕하세요 평범한 컴공생입니다.

 

오늘은 유명한 문제중 하나인 TSP(Traveling Salesman Problem) 알고리즘 포스팅을 해보겠습니다.DFS(Depth First Search)의 대표적인 유형 중 하나인데 저는 c++ 의 STL을 사용하여 문제를 해결하였습니다.

 

실버 2 난이도의 문제입니다

1. 문제 해결 방법 구상하기

 - 들렸던 도시를 다시 방문할 수는 없다.

 - 하지만 모든 도시를 방문해야 한다.

 - 순서가 정해져있다.

 - 그렇다면 순열과 같다.

 - STL 에서 순열함수를 이용하면 된다.

 - 여러 조건을 추가해주어서 조건에 맞는 경우만 최솟값과 비교해준다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <algorithm>

#define MAX 10

using namespace std;

int W[MAX][MAX];
int city[MAX];
int mincost = 987654321;
int N;

int solution()
{
	for (int i = 0; i < N; i++)
		city[i] = i;

	do
	{
		int cost = 0;
		bool all_city = true; // 모든 도시를 다 돌아야만 true 가 유지된다.

		for (int i = 0; i < N-1; i++)
		{
			if (W[city[i]][city[i+1]] > 0)
				cost += W[city[i]][city[i + 1]];
			else
			{
				all_city = false; // 조건 불만족시 all_city의 true 값이 깨짐
				break; // 애초에 조건을 만족하지 못하면 뒤의 연산도 할 필요가 없다.
			}
		}

		if ((W[city[N - 1]][city[0]] > 0) && all_city)
        // 마지막 도시에서 첫번째 도시로 올 때 값까지 확인을 해주어야한다.
		{
			cost += W[city[N - 1]][city[0]];
			mincost = min(mincost, cost);
		}

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

	return mincost;
}

int main()
{
	cin >> N;
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			cin >> W[r][c];

	cout << solution() << endl;

	return 0;
}

직접 순열을 짜는 함수를 dfs로 구현해볼까 했지만 그냥 stl에서 next_permutation 함수를 사용하여 풀었다.

쉽지는 않은 문제였다.

 

// 문제제기 및 피드백 언제든지 감사히 받겠습니다.