문제
풀이
•
완전 탐색으로 풀기
◦
시작 도시 정하기
◦
방문하지 않은 도시들 방문
◦
마지막 도시에서 다시 시작도시로 방문
•
dp 적용
◦
처음 도시에서 다시 처음도시로 돌아가는것이기 때문에 시작 도시가 중요하지 않다.
◦
어자피 사이클이니까 어느 도시에서 시작하든 결과는 똑같다.
◦
첫번째 도시에서 출발하는것으로 고정
◦
현재 방문 상태 + 지금 도시 위치 기준으로 저장
◦
1→2→5→3→4→1
◦
1→5→2→3→4→1
◦
여기서 3→4→1 이 겹침 dp[3][10111]로 해결
•
현재 방문 상태?
◦
방문한 곳을 비트로 표현한다
◦
N ≤ 16 이므로 dp 의 크기는 2^16 이다.
◦
이때 지금 도시 위치에 따라 dp가 달라지기 떄문에
◦
실제 dp의 크기는 16 * 2^16
•
현재 방문 상태만 보고 알수는 없나?
◦
현재 도시에서 출발해야되기 떄문에 현재 방문 상태만으로는 절대 불가능하다
◦
A→B 도시로 이동해놓고 C→D 로 가버릴수있기떄문
•
아직 dp를 이중배열로 생각하는게 서툴다.
구현
#include <iostream>
#include <vector>
#define INF 10000000
using namespace std;
int n;
int W[16][16];
int dp[16][65536];
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
pre();
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> W[i][j];
}
int rec(int curr, int visit) {
int ret;
visit |= (1 << curr);
if (visit == ~(-1 << n))
return (W[curr][0] ? W[curr][0] : INF);
if (dp[curr][visit])
return(dp[curr][visit]);
ret = INF;
for (int i = 1; i < n; i++) {
if ((visit & (1 << i)) || W[curr][i] == 0)
continue;
ret = min(ret, rec(i, visit) + W[curr][i]);
}
dp[curr][visit] = ret;
return (ret);
}
void solve() {
cout << rec(0, 0) << endl;
}
int main(void) {
input();
solve();
return (0);
}
C++
복사
