BOJ 17182 우주 탐사선 /C++

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

17182번: 우주 탐사선

백준 온라인저지 17182번 우주 탐사선 문제입니다.

 

아이디어

모든 행성을 탐사하는데 최소시간을 구해야하는데 행성의 중복방문이 허용이 되기 때문에 행성간의 최소거리 그래프를 구하기 위해 플로이드 와샬 알고리즘을 사용했고, 행성의 방문 여부를 표현하기 위해 비트마스킹을 사용했는데 bitset 자료구조를 사용했습니다. 구해놓은 행성간의 최소거리 그래프를 참고하여 dfs를 이용한 완전탐색으로 풀이했습니다.

 

#include<iostream>
#include<bitset>
#define MAX 51
#define INF 987654321
using namespace std;


bitset<10> bit;
int dist[MAX][MAX];
int map[MAX][MAX];

int n, s;
int minIdx = INF;
int min(int a, int b) { return a > b ? b : a; }

void input() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	}
}


void dfs(int current, int currDist) {

	if (bit.count() == n)
		minIdx = min(currDist, minIdx);


	//최솟값보다 크다면
	if (currDist > minIdx) return;

	//행성 방문
	for (int i = 0; i < n; i++) {
		//현재 방문한 행성이면
		if (bit[i]) continue;
		bit[i] = 1;
		dfs(i, currDist + map[current][i]);
		bit[i] = 0;
	}
}

void solution() {

	//플로이드 와샬
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				if (map[i][j] + map[j][k] < map[i][k])
					map[i][k] = map[i][j] + map[j][k];


	bit[s] = 1;
	dfs(s,0);
	cout << minIdx;
}
int main(void) {
	input();
	solution();
}