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

1. 문제

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

2098번: 외판원 순회

2. 풀이

알고리즘 테스트보다가 만난 문제. 처음에는 N이 16이하라 완전탐색(DFS) 방식으로 풀면 될 것이라 생각했지만 시간초과가 났다. 왜냐하면 모든 경우의 수를 따지면 16!만큼 연산을 해야하기 때문이다.

그리고 모든 점에서 시작하는 경우를 따지지 않아도 된다. 왜냐하면 만약 점 2에서 시작할 때 2 -> 1 -> 3 -> 2 가 최소 비용 경로라고 한다면 1에서 시작할 때도 1 -> 3 -> 2 -> 1 이라는 동일한 최소 비용 경로가 존재하기 때문이다. 따라서 1번 도시부터에서만 시작해서 가장 작은 최소비용을 구하면 되는 것이다.

아래는 완탐으로 푼 내 첫번째 풀이.

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int arr[16][16];
int visit[16] = { 0 };
int answer = 9999999;
int n;

bool isVisitAll() {
	for (int i = 0; i < n; i++) {
		if (visit[i] != 1) {
			return false;
		}
	}
	return true;
}

void dfs(int start, int cur, int total) {
	if (isVisitAll()) {
		total += arr[cur][start];
		if (answer > total) {
			answer = total;
		}
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visit[i] && arr[cur][i] != 0) {
			visit[i] = 1;
			dfs(start, i, total + arr[cur][i]);
			visit[i] = 0;
		}
	}

}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	for (int i = 0; i < n; i++) {
		visit[i] = 1;
		dfs(i, i, 0);
		visit[i] = 0;
	}

	cout << answer << endl;
	return 0;
}

시간초과를 해결하기 위해서는 메모이제이션(dp)과 비트마스크를 이용해야 한다.

 

메모이제이션, 비트마스크 -> 몇 번째 도시를 거쳤는지 기록하기 위함

0번 도시를 거쳤다 라는 것은 비트마스크로 00001 로 표현할 수가 있다. 이 후, 1번 도시를 거치게 된다면 이는 00011 로 표현할 수가 있다. 이 후에 예를 들어 4번 도시를 거쳤다 라고 가정하면10011로 표현을 할 수가 있다. 이 처럼, "현재까지 어느 도시들을 거쳤는지 판단"을 비트마스크로 해 주었다.  결과적으로 모든 도시를 다 방문하게 되면 비트가 '11111'로 표현될 것이다.  이 값은 (1 << N) - 1 로 나타낼 수 있다.

 

cost 배열에서 cost[1][00011] = 8 라면, 이는 "현재 1번 도시이고, 현재 방문 상태는  0번, 1번 도시를 방문 한 상태일 때, 지금까지 든 비용의 최소비용은 8원이라는 것을 의미한다.

 

DFS 함수에서는 시작 정점 0과 현재 상태 bit를 매개변수로 넘겨주었다.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#define INF 9999999
using namespace std;

int arr[16][16];
int cost[16][1 << 16] = { 0 };
int visit[16] = { 0 };
int answer = 9999999;
int n;
int visit_all_bit;


int dfs(int cur, int cur_bit) {
	if (cur_bit == visit_all_bit) {
		if (arr[cur][0] == 0) {
			return INF;
		}
		else {
			//다 방문했으면 원점으로 돌아오는 cost 반환
			return arr[cur][0];
		}
	}

	if (cost[cur][cur_bit] != -1)
		return cost[cur][cur_bit];
	cost[cur][cur_bit] = INF;

	for (int i = 0; i < n; i++) {
		//길이 없거나 방문한 도시는 pass
		if (arr[cur][i] == 0)
			continue;
		if ( (cur_bit & (1 << i)) == (1 << i))
			continue;
		//최소 비용으로 갱신
		cost[cur][cur_bit] = min(cost[cur][cur_bit], arr[cur][i] + dfs(i, cur_bit | 1 << i));
	}
	return cost[cur][cur_bit];
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	visit_all_bit = (1 << n) - 1;

	memset(cost, -1, sizeof(cost));
	cout << dfs(0, 1) << endl;

	return 0;
}

---

*참고

https://yabmoons.tistory.com/358