[BAEKJOON] 2098번 : 외판원 순회*

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

constexpr int INF{ 1'000'000'000 };

int N;
int city[16][16];
int dp[16][1 << 16];

int Circuit(const int& index, const int& bmask) {

	if (bmask == (1 << N) - 1) {
		if (0 == city[index][0]) return INF;
		else					 return city[index][0];
	}

	int& ref{ dp[index][bmask] };
	if (-1 != ref) return ref;

	ref = INF;
	for (int i = 0; i < N; ++i) {
		if (bmask & (1 << i))		continue;
		if (0 == city[index][i])	continue;
		ref = std::min(ref, Circuit(i, bmask | (1 << i)) + city[index][i]);
	}

	return ref;
}

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

	std::cin >> N;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			std::cin >> city[i][j];
		}
	}

	for (int i = 0; i < N; ++i) std::fill_n(dp[i], 1 << 16, -1);


	std::cout << Circuit(0, 1);

}

 

풀 이

 

• dp와 비트마스크의 활용

모든 방문 경로를 dp배열에 담기 위해서는,

1. 한 번 방문한 도시로는 돌아가지 않기 때문에, 마지막으로 방문한 도시로 경로를 나누는데

모든 탐색 후에 최솟 값이 담겨야 하기 때문에,

비트를 통하여 각 마을의 방문 여부를 확인하고 비교해 주면 된다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/2098

2098번: 외판원 순회