백준 2098 외판원순회 c++ // 상태 비트기반 dp, 비트마스킹, 비트 1111 만드는법

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

 

1. 외판원순회 특징

1. {a,b,c} 집합을 "방문"한 상태에서 d로 가는 최소값과

{b,a,c} 집합을 "방문"한 상태에서 d로 가는 최소값은 같다.

즉, {a,b,c} 집합안에서 최소값인 경로(a->b->c 등)는 dp를 채우면서 저장된다.

2. 

2->3->1->2와

3->1->2->2 는 같은 경로이다.

따라서, 출발점은 아무거나(1번도시) 로 하자.

 

1.5. 비트 1111 만드는법

1<<4(1111.size())에서 -1 하면된다!

10000 -1 == 1111

이렇게하면, 모든도시방문한 비트가 만들어진다!

 

2. 의사코드

1. dfs(현재도시, 방문한도시체크용 비트)

dfs(0, 1) 로 시작한다. //(0번도시부터 시작, 0번도시 방문표시==1)

2. 기저사례 : 모든도시를 방문한경우, 다시 출발점(0번도시로 돌아간다)

3. if(dp!=-1) : 계산된 값이 있으면 그거리턴

4. 논리식

4.0. 초기화 : 987654321로 초기화한다.

모든 도시를 돌며 방문안한 도시(i)로 들어간다.

4.1. 이미방문한경우 or 갈수없는경우는 continue

4.2 dp = min( dp, dfs(i, i도시 비트추가) + i도시로 가는비용)

최초로 돌아올때, 그 값(4->1)부터 맨뒤에서 시작한다.

돌아오면서 최소값을 저장한다.

2회차부터는, 이전에 저장된 최소값(9)와

새로계산된 5+2 중 최소값을 기록한다... 반복????????????

값이 있으면 바로리턴인데 뭔가 이상함... 이해가 덜된듯

 

 

3.전체코드

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int n, w[16][16],dp[16][1<<16]; 
//[현재위치][방문한비트] : [방문비트]방문시 최소비용

int dfs(int here, int visited) {
	//모든지점을 방문한경우
	// ex ) 도시4개 : 1111
	// 10000(1<<4) 에서 -1 하면 1111이 된다!
	if (visited == (1 << n) - 1) {
		//다시 출발점(0번도시)로 갈수있으면 간다.
		if (w[here][0]) {
			return w[here][0];
		} //갈수없는 경로이면 배제시킴
		else return 987654321;
	}
	//계산된값이 있는경우 그거리턴
	if (dp[here][visited] != -1) return dp[here][visited];

	//초기값 = 최대로설정 (최소값 구하기니까)
	dp[here][visited] = 987654321;
	//모든도시를 돌며, 방문안한곳으로 들어감!
	//i번째 도시로 갈 예정임.
	for (int i = 0; i < n; ++i) {
		//i번째 도시를 이미 방문했으면 탐색안함
		if (visited & (1 << i)) continue;
		if (w[here][i] == 0) continue; //갈수없는경우
		//i번째 도시 방문체크후, 그 비용을 더함
		dp[here][visited] = min(dp[here][visited], 
			dfs(i, visited | (1 << i)) + w[here][i]);
	}
	return dp[here][visited];


}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> w[i][j];
		}
	}
	//memset(dp, -1, sizeof(dp));
	fill(&dp[0][0], &dp[0][0] + 16 * (1 << 16), -1);
	//[현재 : 0번도시] [0번도시 방문표시 비트키기]
	cout << dfs(0, 1);

	return 0;
}

 

5. 의문점

1. 애초에 dp를 987654321 로 초기화하면 되지않나? -> 시간초과 -> ??

큰돌님께 질의 올려놓음

 

 

if(dp!=-1) return dp //방문한 경우, return dp

for문이 동작안하는경우 -> dp=987654321, but 해당상태는 방문(계산)된 상태임.

dp = 987654321 이면, 계산된것임! (도달불가능하다는 계산이 완료됬다고 생각)-> 즉시 987654321 리턴.

초기화 = 987654321 하고
dp != 987654321 return dp 하면,
987654321 의 의미가 계산이 안됬다는것인지, 계산했는데 안유망 하다는것인지 몰라서
계산했는데 안유망한경우도 재탐색 -> 시간초과 발생!

 

2. 결론 : 초기화를 -1로하고, dfs들어가기전 초기화(987654321)를 따로하자!

-1의 의미 : 계산안했음

987654321의 의미 : 계산했으나, ~유망