백준 17182번

백준 17182번 (우주탐사선)

우주 탐사선이 주어진 모든 행성을 방문할 경우 걸리는 가장 최단 시간을 구하는 문제이다. 행성의 갯수와 시작 행성, 그리고 각 행성까지 걸리는 시간이 배열 형식으로 주어진다.

처음에는 문제를 오해하여 플로이드 와샬로 풀려했다. 모든 행성을 방문해야하는데 각 행성의 방문하여 그 총합 시간의 최소로 오해하였다... 문제를 천천히 잘 이해하는 것의 중요성을 느꼈다...🤣

해당 문제는 다익스트라 알고리즘과 비트마스크를 이용하여 해결하는 문제이다. 해당 문제에서 비트마스크의 역할은 모든 행성을 방문하였는지 점검해주는 역할을 한다. 그리고 최단 시간은 다익스트라 알고리즘을 통해 구해준다. matrix 배열에는 각 행성까지 걸리는 시간을 저장해주고, chk[i][j]의 의미는 i의 비트마스크로 현재까지 방문한 행성을 구분해주고, j로 출발점부터 지금까지 걸린 시간을 확인해준다.

#include <bits/stdc++.h>

using namespace std;

int matrix[11][11];
int chk[1 << 11][11];

struct EDGE {
	int num, check, time;
};

bool operator < (EDGE e1, EDGE e2) {
	return e1.time > e2.time;
}

// 다익스트라 + 비트마스트
int main() {
	int n, k;
	memset(chk, 0x3f, sizeof(chk));
	scanf_s("%d %d", &n, &k);

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			scanf_s("%d", &matrix[i][j]);

	int answer = 0;
	priority_queue<EDGE> pq;
	pq.push({ k, 1 << k, 0 });
	while (pq.size()) {
		auto num = pq.top().num;
		auto check = pq.top().check;
		auto time = pq.top().time;
		pq.pop();
		if (check == (1 << n) - 1) {
			answer = time;
			break;
		}
		for (int i = 0; i < n; i++) {
			if (i == num)
				continue;
			if (time + matrix[num][i] < chk[check][i]) {
				chk[check][i] = time + matrix[num][i];
				pq.push({ i, check | (1 << i), chk[check][i] });
			}
		}
	}

	printf("%d", answer);

	return 0;
}