BOJ-2098-외판원 순회

[changicho]

2098. 외판원 순회

링크

난이도	정답률(_%)
Gold I	26.492

설계

동적계획법

정리

내 코드 (ms)	빠른 코드 (ms)
24

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <limits>

#define SIZE 16 + 1
#define INF 1000000000

using namespace std;

int N;
int graph[SIZE][SIZE];
int dp[SIZE][1 << 16];

int tsp(int curr, int visited) {	//현재 몇번 째 마을에 위치하는지, 어느 마을을 방문하고 왔는지
	int ret = dp[curr][visited];

	if (dp[curr][visited] != 0)		//이미 구한 적 있다면
		return dp[curr][visited];

	if (visited == (1 << N) - 1) {	//모든 마을 방문했을 때
		if (graph[curr][0] != 0) {	//0번 마을로 갈 수 있을 때
			return graph[curr][0];
		}

		return INF;					//불가능 하도록 매우 큰 수를 return
	}

	dp[curr][visited] = INF;

	for (int i = 0; i<N; i++) {
		if ((visited & 1 << i) || (graph[curr][i] == 0)) //i번째 visited 를 확인하기 위한 bit 연산
			continue;
		
		dp[curr][visited] = min(dp[curr][visited], tsp(i, (visited | 1 << i)) + graph[curr][i]);
	}

	return dp[curr][visited];
}

void solution() {
	cin >> N;

	for (int from = 0; from < N; from++) {
		for (int to = 0; to < N; to++) {
			cin >> graph[from][to];
		}
	}

	int answer = tsp(0, 1);

	cout << answer << "\n";
}

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

	solution();

	return 0;
}