[백준][2098] 외판원 순회

이 포스트는 백준 사이트의 외판원 순회 문제 풀이입니다.

문제

해결 과정

이 문제는 비트마스킹과 메모이제이션 기법을 사용하면 제한시간 안에 결과를 확인할 수 있습니다.

문제가 요구하는 결과는 모든 지점을 방문할 때, 비용의 최솟값입니다.
이 값을 구하기 위해 모든 지점에서 매번 새롭게 비용을 구한다면
시간초과로 인해서 제한시간 안에 해결할 수 없습니다.

따라서 실행 시간을 단축시키기 위해
모든 도시를 재방문하지 않고 최초 1회만 방문하여 최솟값을 구하고자 하였습니다.
그리고 재방문 기록을 위해서는 boolean 배열이 아니라 비트 연산자를 사용해 보았습니다.

코드 구현

#include <iostream>

using namespace std;

int N;
int DP[16][1 << 16];	//: [현재 도시 위치][방문했던 도시를 비트마크로]
int cost_map[16][16];	//: (N x N) 형식 비용 표

int TSP(int curr, int visited);


int main(){
	ios::sync_with_io(false);
	cin.tie(0);

	cin >> N;

	for (int start = 0, cost; start < N; ++start)
	{
		for (int end = 0; end < N; ++end)
		{
			cin >> cost;
			cost_map[start][end] = cost;
		}
	}

	cout << TSP(0, 1);
	return 0;
}


int TSP(int curr, int visited) {		// curr: 시작위치, visited: bit로 표현한 방문기록
	if (visited == ((1 << N) - 1)) {	// 모든 도시 방문 완료.
		if (0 == cost_map[curr][0])		// 현위치에서 0번으로 돌아갈 수 없음.
			return 2e9;
		else
			return cost_map[curr][0];	// 돌아갈 수 있음.
	}
	
	if (false != DP[curr][visited])	// 이미 방문함.
		return DP[curr][visited];

	DP[curr][visited] = 2e9;	// 첫 방문이므로 최소비용 비교를 위해 최댓값 초기화.

	// bit masking을 사용해 0번부터 N - 1번 노드까지
	// 현재 위치랑 연결되어 있는지 확인
	for (int bit_mask = 0; bit_mask < N; ++bit_mask) {
		int next = 1 << bit_mask;

		// 연결(curr->bit_mask)이 안됨 || 이미 방문 했었음.
		if ((0 == cost_map[curr][bit_mask]) || (0 < (visited & next)))
			continue;

		// 현재 노드에서 visited에 비트로 작성된 도시 방문 중 최소값
		DP[curr][visited] = min(
			DP[curr][visited], 
			TSP(bit_mask, visited | next) + cost_map[curr][bit_mask]
		);
	}

	return DP[curr][visited];
}

실행 결과