Boj 2098) 외판원 순회

문제

백준 2098

설명

비트마스크를 이용한 DP 로 풀 수 있는 문제이다.

이때 2가지 주의사항이 있다.

1. 방문한 지점이 달라도 시작지점이 다르면 결과가 다르므로 2차원 DP 배열을 써야한다.
2. 아래 삽질처럼 dp[][] 배열을 잘못잡아서 한번 평가한 결과를 더 나은 경우로 다시 평가해야하면 시간초과가 난다. 현재 위치가 pos 이고 방문상태가 visits 일 때dp[pos][visits] 를 원점으로 돌아가기 위한 비용으로 두면 이런 상황이 발생하지 않는다.
3. 모든 정점을 방문하는 것이 아니라 원점으로 돌아와야 하는 것이므로, 맨 마지막에만 원점으로 돌아가도록 구현해야한다. 위 코드는 처음에 visits 을 1을 둬서 원점인 0번에 중간에 갈 수 없도록 하였고, 마지막에 visits 가 꽉 차면 원점인 0으로 가도록 하는 방식으로 구현하였다.

시간 복잡도

O(n^2*2^n)

코드

int board[16][16], dp[16][1 << 16], n;
int DFS(int cur, int visits)
{
	if (visits == (1 << n) - 1)  // 모두 방문했으면 처음 위치인 0 으로 돌아간다.
        return board[cur][0] ? board[cur][0] : 1e9;
	if (dp[cur][visits])         // dp 중복 계산 방지
        return dp[cur][visits]-1;
    
	dp[cur][visits] = 1e9;
	for (int i = 0; i < n; i++)
	{
		if (visits & (1 << i) || board[cur][i] == 0) continue;
		dp[cur][visits] = min(dp[cur][visits], DFS(i, visits | (1 << i)) + board[cur][i]);
	}
	
	return dp[cur][visits]++;    // 미리 1을 더해서 dp[][] 의 기본값인 0 과 구별할 수 있게 한다.
}

int main()
{
	fastio;

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];
	
	cout << DFS(0, 1);           // 0번을 미리 방문시켜(visits <= 1) 중간에 0번으로 가지 않도록 한다.
}

삽질

코드

int board[16][16], dp[16][1 << 16], n;
void DFS(int cur, int visits)
{
	for (int i = 0; i < n; i++)
	{
		if (visits & (1 << i) || board[cur][i] == 0) continue;
		if (dp[cur][visits] + board[cur][i] < dp[i][visits | (1 << i)])
		{
			dp[i][visits | (1 << i)] = dp[cur][visits] + board[cur][i];
			DFS(i, visits | (1 << i));
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	fill(dp[0], dp[16], 1e9); dp[0][0] = 0;
	int mask = 0;
	for (int i = 0; i < n; i++) mask |= 1 << i;
	DFS(0, 0);
	cout << dp[0][mask];
}

설명

위 방법은 dp[pos][visits] 를 visits 만큼 방문해서 pos 위치에 도달하기까지 걸리는 비용을 두었다. 이러한 dp[][] 는 재평가될 가능성이 크다. 그리고 한번 재평가되면 이 값을 기준으로 평가한 다른 dp[][] 값들도 재평가를 해야한다. 그래서 시간초과가 뜬다.