2098 TSP

์•Œ๊ณ ๋ฆฌ์ฆ˜(์™ธํŒ์› ์ˆœํšŒ, DP, ๋น„ํŠธ๋งˆ์Šคํฌ)

1. ๋น„ํŠธ๋งˆ์Šคํฌ๋กœ ๊ฐ ๋น„ํŠธ๋งˆ๋‹ค ํ•˜๋‚˜์˜ ๋„์‹œ๋ผ๊ณ  ์น˜๊ณ , ๊ฒ€์‚ฌ๋ฅผ ํ•จ.
2. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๊ณ , ๊ฐˆ์ˆ˜ ์žˆ๋Š” ๋„์‹œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ์‹์œผ๋กœ ๋๊นŒ์ง€๊ฐ.
	-> ๋๊นŒ์ง€ ๊ฐ”์„ ๋•Œ ๋‹ค์‹œ ๋Œ์•„๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด ์žˆ์œผ๋ฉด ๊ทธ ๊ฐ’ ๋ฐ˜ํ™˜, ์—†์œผ๋ฉด IMPOSSIBLE ๋ฐ˜ํ™˜
	-> ๊ทธ ์ „ ์žฌ๊ท€๋กœ ๋Œ์•„์™€์„œ ๊ฐ€์žฅ ์ตœ์†Ÿ๊ฐ’์„ dp[current][bitMask] ์— ์ €์žฅํ•จ.
3. ๊ฐ ์žฌ๊ท€ ์ฒ˜์Œ์—” ๋Œ์•„๊ฐˆ ์ˆ˜ ๋งˆ์ง€๋ง‰์ธ์ง€ ํ™•์ธํ•˜๊ณ , ์ด๋ฏธ ๋ฐฉ๋ฌธ๋๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

์ƒˆ๊ฒจ๋‘˜ ์ .

1. ๋ชจ๋“  ์ถœ๋ฐœ์ ์— ๋Œ€ํ•ด ์‹คํ–‰ํ•  ํ•„์š”๋Š” ์—†๋‹ค.
	-> ์ตœ์†Œ๋กœ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ๊ฐ€ ์žˆ์„ ๋•Œ, ์–ด๋””์„œ ์ถœ๋ฐœํ•˜๋“  ๊ทธ ๊ฐ’์€ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์—.
2. ๋๊นŒ์ง€ ๊ฐ”์„ ๋•Œ, ๊ทธ๋•Œ๋ถ€ํ„ฐ ๊ฐ’์„ ํ•˜๋‚˜์”ฉ ๋”ํ•ด์˜ค๋Š” ์‹์œผ๋กœ ๊ณ„์‚ฐํ•œ๋‹ค.
	-> ๊ฐ’์„ ๋“ค๊ณ ๊ฐ€๋ฉด INFINITY๊ฐ’๊ณผ ์ถฉ๋Œ์„ ์ผ์œผ์ผœ ์ž˜๋ชป๋œ ๊ฐ’์ด ๋ฐ˜ํ™˜๋  ์ˆ˜ ์žˆ๊ฒŒ๋จ.
	-> ๋˜ ์ด๋ ‡๊ฒŒํ•˜๋ฉด ์ž๋™์œผ๋กœ dp์—” ์ดํ›„ ๊ฒฝ๋กœ์˜ ์ตœ์†Ÿ๊ฐ’์ด ์ €์žฅ๋จ.
3. ๋”ฐ๋ผ์„œ ๊ฐ ๋‹จ๊ณ„์—์„œ ์ตœ์†Ÿ๊ฐ’์ด INFINITY ๊ฐ’์ด๋ผ ํ•˜๋”๋ผ๋„ ๋ฌด์กฐ๊ฑด dp์— ์ €์žฅํ•˜์ž.
	-> INFINITY๊ฐ’์ด ์ €์žฅ๋๋‹ค๋Š” ๊ฑฐ๋Š”, ํ˜„์žฌ์ƒํƒœ์—์„œ ์ˆœํšŒํ•  ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด ์—†๋‹ค๋Š” ๋œป์ด๋ฏ€๋กœ.
4. INFINITY๊ฐ’์„ ์ง€์ •ํ•  ๋•, ํ˜„์žฌ value๊ฐ’์„ ๋”ํ•ด๋„ ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋„๋ก ์ง€์ •ํ•ด๋‘˜ ํ•„์š”๊ฐ€ ์žˆ๋‹ค.
5. ๋น„ํŠธ๋งˆ์Šคํฌ๋กœ ๊ฐ ๋„์‹œ๊ฐ€ ์ด๋ฏธ ๋ฐฉ๋ฌธ๋๋Š”์ง€ ํ™•์ธํ•˜๋Š” ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
	 bitMask & (1 << i)
 ์ด๋ฏธ ๋ฐฉ๋ฌธ๋๋‹ค๋ฉด ์ด ๊ฐ’์€ ์ฐธ์„ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ๋œ๋‹ค. ( 1011 & 0010 => 0010 => ์ฐธ  / 1011 & 0100 => 0000 => ๊ฑฐ์ง“)

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_TOWN 16
#define INFINITY 2000000123
 
using namespace std;
 
bool check[MAX_TOWN];
int dp[MAX_TOWN][1 << MAX_TOWN];
int map[MAX_TOWN][MAX_TOWN];
int numOfTown, start, endBit;
 
int getMinValue(int current, int bitMask);
int min(int a, int b);
 
int main() {
	cin >> numOfTown;
	for (int i = 0; i < numOfTown; i++)
		for (int j = 0; j < numOfTown; j++) {
			cin >> map[i][j];
		}
 
	endBit = (1 << numOfTown) - 1;
	memset(dp, -1, sizeof(dp));
	check[0] = true;
	start = 0;
	cout << getMinValue(0, 1);
}
 
int min(int a, int b) {
	return a < b ? a : b;
}
 
int getMinValue(int current,int bitMask) {
	if (bitMask == endBit) {
		if (map[current][start] == 0)
			return INFINITY;
		return map[current][start];
	}
	if (dp[current][bitMask] != -1)
		return dp[current][bitMask];
 
	int tempMin = INFINITY;
	for (int i = 0; i < numOfTown; i++) {
		if (!check[i] && map[current][i] != 0) {
			check[i] = true;
			tempMin = min(tempMin, map[current][i] + getMinValue(i, bitMask + (1 << i)));
			check[i] = false;
		}
	}
	return dp[current][bitMask] = tempMin;
}