백준 C++ 외판원 순회 2

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

10971번: 외판원 순회 2

그냥 간단한 외판원 문제입니다. 외판원 문제가 오랜만에 보여서 풀어보았는데 틀렸다고 해서 다른 외판원 문제 풀었던 코드로 넣으니 정답이 나왔습니다. (왜지???? 전혀 다른 점이 없었는데??? 눈을 잘 비벼보자.....)

 

특별한 조건은 없고, weight 가 항상 양수인 조건만 있습니다. 외판원이 노드를 방문하는 과정에서

dp[i][j] = i 번 노드 현재 방문 중일 때 바이너리값 j 만큼 지나왔고, 그 때 지나온 경로의 최소값

으로 잡으면 됩니다.

그리고 해당 노드가 방문 가능할 때 dp 값을 업데이트하면 됩니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int w[11][11]; // 가중치
int dp[11][1 << 11]; // dp 값
// dp[i][j] : i 번 노드 방문, j 만큼 탐색했었을 때
// 경로 합 최소값
int INF = 987654321;

int tsp(int now, int visited)
{
  	// weight 양수
  	// 계산된 결과 존재
	if (dp[now][visited] != 0)
		return dp[now][visited];

  	// 다 지나옴
	if (visited == (1 << n) - 1)
	{
    	// 시작점 0과 연결된 길 있음
		if (w[now][0] != 0)
			return w[now][0];
        // 없음
		return INF;
	}
  
	dp[now][visited] = INF;
	for (int i = 0; i < n; i++)
	{
    	// 지나왔었거나 길 없음
		if ((visited & (1 << i)) || (w[now][i] == 0))
			continue;
    	// i번부터 재탐색하고 dp 값 업데이트
		int tmp = tsp(i, (visited | (1 << i))) + w[now][i];
		dp[now][visited] = min(dp[now][visited], tmp);
	}
  
	return dp[now][visited];
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> w[i][j];
	cout << tsp(0, 1);
}