[백준] 17182번. 우주 탐사선 (C++)

문제

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

 

풀이

DFS+플로이드 와샬

1. Floyd-Warshall

행성A에서 행성 B로 가는 방법은 한가지가 아니다!

A-C-B, A-B, A-C-D-B 등등.. 많다

이 중에 어떠한 것이 최소 경로인지 파악하기 위해 플로이드 와샬을 쓴다

 

플로이드 와샬 전 → 후

case1

0 30 1       0 2 1
1 0 29  -->  1 0 2
28 1 0       2 1 0

case2

0 83 38 7        0 53 38 7
15 0 30 83       15 0 30 22
67 99 0 44  -->  58 90 0 44
14 46 81 0       14 46 52 0

 

+) 플로이드 와샬 알고리즘 설명

https://yun000.tistory.com/155

플로이드 와샬 알고리즘(Floyd Warshall)

 

 

2. DFS

이제 최소 경로를 아니

K부터 시작해서 DFS로 탐색을 쭉 하면 된다~

 

+) 재귀함수 종료 조건

sum>answer이면 더 봐봤자 정답이 아니니 return

모두 다 탐색했으면 (즉 exploreCount==N) 최단 이동거리를 answer로 정하고 return

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;
vector<int>visit;
vector<vector<int>>graph;
int answer = 2000000;

void dfs(int node, int sum, int exploreCount)
{
	if (sum >= answer) { return; }

	if (exploreCount==N) //explore complete!
	{	answer = min(sum, answer); return;	}

	for (int i = 0; i <N; i++)
	{
		if (visit[i]==1)continue;
		visit[i] = 1;
		dfs(i, sum + graph[node][i], exploreCount+1);
		visit[i] = 0;
	}
}

int main()
{
	//INPUT
	cin >> N >> K;
	graph= vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < N; k++)
		{  cin >> graph[i][k];  }
	}

	//Floyd-Warshall
	for (int k = 0; k < N; k++) 
	{
		for (int i = 0; i < N; i++) 
		{
			for (int j = 0; j < N; j++) 
			{	graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);	}
		}
	}

	//EXPLORE!!
	visit= vector<int>(N, 0);
	visit[K] = 1;
	dfs(K, 0, 1);

	//RESULT
	cout << answer;
}

 

처음에는 그냥 DFS쓰면 되겄네 해서 작성했는데 되지 않았다.

그래서 별 이상한 방법을 다 쓰다가

검색 후 플로이드 와샬 방법을 사용하게 되었다