[백준/BOJ] 백준 2098번 : 외판원 순회

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

2098번: 외판원 순회

cache[16][(1 << 16)]; 에 [위치][방문 상황(방문 위치 상황을 비트로 표현)] = 순회에 필요한 최소 비용을 저장하여 다이나믹 프로그래밍으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int adj[16][16]; //그래프
int cache[16][(1 << 16)]; //[위치][방문 상황] = 순회에 필요한 최소 비용

void Pre()
{
	for (int i = 0; i < 16; i++)
		for (int j = 0; j < (1 << 16); j++)
			cache[i][j] = -1;
}

int Solve(int here, int status)
{
	//모든 경로를 다 탐색 했을때
	if (status == (1 << n) - 1)
	{
		//출발지점(0번 정점)으로 돌아갈 수 있을때
		if (adj[here][0] != 0)
			return adj[here][0];

		//출발지점으로 돌아갈 수 없을때
		else
			return 987654321;
	}

	int& ret = cache[here][status];

	if (ret != -1)
		return ret;

	ret = 987654321;

	for (int i = 0; i < n; i++)
	{
		//i가 방문한적이 없는 곳이고 갈 수 있는 길이 있을때
		if ((((status & (1 << i)) == 0)) && (adj[here][i] != 0))
		{
			status ^= (1 << i);
			ret = min(ret, Solve(i, status) + adj[here][i]);
			status ^= (1 << i);
		}
	}

	return ret;
}

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

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;

			cin >> input;

			adj[i][j] = input;
		}
	}

	//모든 위치를 돌아서 시작점으로 돌아오는 순환을 하므로 어디서 시작하던지 상관없다
	//출발지를 0번도시에서 시작
	cout << Solve(0, 1);

	return 0;
}