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;
}