[백준 17182] 우주 탐사선 c++ (플로이드 + 완전탐색 )

문제 링크

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

17182번: 우주 탐사선

 

문제 풀이

문제를 유심히 읽어야한다.   K 번행성에서 시작해서 모든 행성을 거치는 최단경로를 찾는 것이다.

하지만 주의할 점이 a->b에 경로가 잇더라도, a->c->b와 같이 다른 곳을 거치는 것이 더 빠른 경로일 수 도 있다는 것이다.

따라서 각 정점들간의 최단 거리를 플로이드 와샬을 통해 구하는 것으로 '실제 각 정점간 최단거리' 를 찾은 뒤, 정점 방문 순서의 모든 경우의 수를 완전탐색(permutation) 으로 탐색하며 각 경우의 수에서의 '전체 방문 시간' 을 찾는다.

이중 '최단 거리' 인 것을 출력하면 끝이다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;
#include<math.h>
//2:00 ~ 2:40
struct Edge {
	int a;
	int b;
	int cost;
	bool operator <(Edge other)const  {
		return cost > other.cost;
	}
};

int parent[11];

int find(int a) {
	if (parent[a] == a)return a;
	parent[a] = find(parent[a]);
	return parent[a];
}

void join(int a, int b) {
	parent[a] = b;
}
int arr[11][11];
int dist[11][11];//dp
int visit[11];
int answer = 987654321;
int N, K;
void per(int now,int depth,int sum) {
	if (depth == N-1) {
		if (answer > sum)answer = sum;
		return;
	}
	for (int i = 0; i < N; i++) {
		if (visit[i])continue;
		visit[i] = 1;
		per(i,depth+1,sum+dist[now][i]);
		visit[i] = 0;
	}
}

int main() {
	
	vector<pair<int, int>> e[11];
	priority_queue<Edge> pq;
	cin >> N >> K;
	int a, b, c;
	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++) {
			cin >> dist[i][j];
		}
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	//완탐으로 행성 방문 순서정하자( 첫방문 )
	// 위와 같이 플로이드 적용하는 것으로 어딘가 거쳐서 가는 경우의 수 고려한 최단거리값이 적용된다.	visit[K] = 1;
	visit[K] = 1;
	per(K, 0, 0);
	
	cout << answer;
}