[백준 10971, c++] 외판원 순회2(DFS)

문제 번호

• 10971(https://www.acmicpc.net/problem/10971)

문제 및 입/출력

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

• 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 
• 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)
• 이러한 여행 경로는 여러 가지가 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
• 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.
• 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 
• 모든 도시간의 비용은 양의 정수이다. 
• W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
• N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

 

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 

예제 입력

4  0 10 15 20  5  0  9 10  6 13  0 12  8  8  9  0

 

예제 출력

35

 

문제 풀이

• 각각의 도시에서 깊이 우선 탐색(Depth First Search)를 사용하여 전체를 탐색한다.
• 재귀함수를 통한 탐색을 진행하다가 종료조건(n개의 도시를 전부 방문했고(cnt==n), 다시 출발했던 도시로 돌아온 경우(start_node == row)) 를 만족했을때 빠져나온다.
• 방문하는 도시를 거치는 도중에 Cost를 더하면서 탐색을 진행한다.
• 방문한 도시는 visited에 true값을 갖는다.
• 소스코드를 두 가지를 올려놓은 것은 첫번째 소스의 경우 정말 전체를 탐색하는 경우이고, 두번째 소스의 경우에는 탐색중에 sum이 최소값인 minCost보다 큰 경우 더 이상 탐색을 진행하지 않는다. 이 두 가지 소스는 상당한 차이를 보인다. (문제에 주어진 조건에 맞춰서 이러한 설정을 해줄 수 있는 것이 중요하다라는 것을 느꼈다)

소스 코드

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

#include <iostream>

using namespace std;

#define MAX 10 // 최대로 주어질 수 있는 도시의 수

int n;
int arr[MAX][MAX];
int visited[MAX];
int minCost = 0;

int user_min(int x, int y) { if (x < y) return x; return y; }

void depth_first_search(int start_node, int row, int sum, int cnt) {
	if (!visited[row]) {
		visited[row] = true;
		for (int col = 0; col < n; col++) {
			if (arr[row][col]) {
				depth_first_search(start_node, col, sum + arr[row][col], cnt + 1);
			}
		}
		visited[row] = false;
	}

	/* n개의 도시를 방문했고(cnt==n), 다시 출발한 도시로 돌아 온 경우(start_node==row)*/
	if (cnt == n && start_node == row) {
		minCost = (minCost == 0) ? sum : user_min(sum, minCost);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	/* 입력단 */
	cin >> n;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			cin >> arr[row][col];
		}
	}

	/* 문제풀이 */
	for (int row = 0; row < n; row++) {
		depth_first_search(row,row,0,0);
	}

	/* 출력단 */
	cout << minCost << "\n";

	return 0;
}

 

 

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

#include <iostream>

using namespace std;

#define MAX 10 // 최대로 주어질 수 있는 도시의 수

int n;
int arr[MAX][MAX];
int visited[MAX];
int minCost = 987654321;

void depth_first_search(int start_node, int row, int sum, int cnt) {
	/* n개의 도시를 방문했고(cnt==n), 다시 출발한 도시로 돌아 온 경우(start_node==row)*/
	if (cnt == n && start_node == row) {
		if (minCost > sum) minCost = sum;
		return;
	}
	
	for (int col = 0; col < n; col++) {
		if (!arr[row][col]) continue;

		if (!visited[row]) {
			visited[row] = true;
			sum += arr[row][col];
			if (sum <= minCost) {
				depth_first_search(start_node, col, sum, cnt + 1);
			}
			visited[row] = false;
			sum -= arr[row][col];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	/* 입력단 */
	cin >> n;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			cin >> arr[row][col];
		}
	}

	/* 문제풀이 */
	for (int row = 0; row < n; row++) {
		depth_first_search(row,row,0,0);
	}

	/* 출력단 */
	cout << minCost << "\n";

	return 0;
}