백준 10971번 : 외판원 순회 2 - 비트마스킹 BFS C++

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

10971번: 외판원 순회 2

1. 문제설명

외판원 순회 문제입니다.

시작점을 정해주지 않았기 때문에 모든 노드에서 시작할 수 있습니다.

우선순위큐를 이용해서 최단거리를 우선으로 방문해야 메모리와 시간을 아낄 수 있습니다.

 

 

시험삼아 우선순위큐만 큐로 바꿔서 돌려봤습니다.

 

메모리 63072KB, 360ms 걸린 게 일반 큐를 이용한 것이고

메모리 2500KB, 4ms가 우선순위 큐를 이용한 것입니다.

 

메모리와 시간차이가 나는 이유는

우선순위큐를 이용할 때는 최단거리를 우선으로 방문하고 그 이외에는 방문하지 않는데

큐를 이용할 때는 이미 방문했던 점이 최단거리가 아닐 수 있기 때문에

계속해서 해당 노드의 해당 상태에 대해 불필요한 계산이 이루어져서

시간과 메모리가 많이 사용됩니다.

 

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

int ch[11][1 << 11];
int n, arr[11][11];

struct Node {
	int cur, vis, st, dist;
	bool operator<(const Node& b) const {
		return dist > b.dist;
	}
};

using namespace std;
int main() {


	priority_queue<Node> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		Q.push({ i,1 << i,i ,0 });
	}

	int ans = INT_MAX;

	while (!Q.empty()) {
		int cur = Q.top().cur;
		int vis = Q.top().vis;
		int st = Q.top().st;
		int dist = Q.top().dist;
		Q.pop();

		ch[cur][vis] = 1;

		if (vis == (1 << n) - 1) {
			if (arr[cur][st] != 0) ans = min(ans, dist + arr[cur][st]);
		}

		for (int i = 0; i < n; i++) {
			if (arr[cur][i] > 0 && ch[cur][vis | (1 << i)] == 0) {
				Q.push({ i,vis | (1 << i),st,dist + arr[cur][i] });
			}
		}
	}
	cout << ans << '\n';


	return 0;
}

백준 10971번 외판원 순회