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

백준 17182 우주탐사선

1. 문제

문제링크

2. 접근법

• 문제 접근
  • 모든 행성을 탐사하기 위해 임의의 행성 A에서 행성 B로 이동할 때 걸리는 최소시간을 구해야 한다.
  • 이때 플로이드 와샬 알고리즘을 사용하여 거쳐가는 노드를 생성하고, 만약 행성 A -> 행성 C-> 행성 B까지 걸리는 시간이 행성 A-> 행성 B 까지 걸리는 시간보다 짧다면 2차원 행렬에 해당 값(최솟값)을 업데이트 시킨다.
  • N값이 충분히 작기 때문에 완전탐색을 사용하는 DFS 알고리즘을 사용하였다.
  • DFS의 매개변수는 행성의 인덱스, 방문한 행성의 수, 걸리는 시간으로 두고,
  • 모든 행성의 방문여부를 체크하기 위해 체크배열을 생성한다.
  • 입력받은 행성의 수만큼 for문을 돌면서 각 행성을 방문하지 않은 경우 방문여부를 true로 만들고 DFS 재귀함수를 호출한다. -> 이때 걸리는 시간은 처음 매개변수로 받은 행성에서 새로 탐사할 행성까지 걸리는 시간을 더한 값이다.
  • 모든 가능한 노드를 살펴봐야 하므로 재귀호출한 DFS를 다 돌고나면 체크배열의 방문여부를 0 으로 바꿔준다.
  • 위 문제에서 이미 방문한 행성도 중복해서 갈 수 있다는 조건이 있는데 이미 플로이드 와샬 알고리즘을 사용하여 최솟값을 업데이트 시켜줬으므로 한번 더 방문할 필요가 없다. 

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cstring>
#include<fstream>
#define MAX 987654321
using namespace std;
int map[10][10];
bool checked[10];
int ans = MAX;
int node, pos;
void DFS(int idx, int cnt, int dis)
{
	if (ans < dis)
		return;
	if (cnt == node)
	{
		ans = min(ans, dis);
		return;
	}
	for (int i = 0; i < node; i++)
	{
		if (checked[i])
			continue;
		checked[i] = 1;
		DFS(i, cnt + 1, dis + map[idx][i]);
		checked[i] = 0;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(checked, false, sizeof(checked));
	cin >> node >> pos;

	for (int i = 0; i < node; i++)
	{
		for (int j = 0; j < node; j++)
		{
			cin >> map[i][j];
		}
	}
	checked[pos] = true;
	//플로이드와샬
	for (int k = 0; k < node; k++)
	{
		for (int i = 0; i < node; i++)
		{
			for (int j = 0; j < node; j++)
			{
				if (map[i][k] + map[k][j] < map[i][j])
					map[i][j] = map[i][k] + map[k][j];
			}
		}
	}

	DFS(pos, 1, 0);
	cout << ans << "\n";
	return 0;
}

4. 시간복잡도

DFS 알고리즘에서 인접리스트 이용한 방법이므로 기본적으로 O(V+E)의 시간복잡도를 가진다.
여기서 플로이드 와샬은 3개의 반복문을 통해 O(N^3)의 시간복잡도를 가지는데 N이 10 즉 1000으로 구현하기 위한 시간은 충분하다.

따라서 위 코드의 시간복잡도는 O(V^3)+O(V+E)이 된다.

 

5. 결과

6. 추가 문제

• 플로이드 와샬: 프로그래머스 '순위' 문제 풀어보기