[BOJ/백준 17182/C++] 우주 탐사선

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

17182번: 우주 탐사선

 

[문제 요약]

- 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다.

 

- 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다.

 

- 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다.

 

- 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

 

- 탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

 

[문제 조건]

- 첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

 

- 다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

 

- 시간 제한 : 1초

- 메모리 제한 : 512MB

 

[문제 풀이]

문제를 읽어보면 한 위치에서 시작하여 "모든" 행성을 탐색하는 최소 시간을 구해야 한다.

 

이럴때 쓰는 방법은 플로이드-와샬 방법을 이용하면 쉽게 구할 수 있을 것이다.

 

왜냐하면 모든 정점에 대해서 다른 모든 정점으로의 (최소,최단) 값들이 필요하기 때문이다.

 

근데 문제 마지막에 이상한 문장이 하나 있다. "탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 "이미 방문한 행성도 중복해서 갈 수 있다."

 

중복 방문이 허용된다는 것이다.

 

근데 잘 생각해보면 문제 조건에서 행성간 이동시간은 항상 0보다 크다. 그렇다는 것은 음의 가중치를 갖는 시간이 존재하지 않는 것이다. 따라서 그냥 무시하고 생각해도 상관 없다는 뜻이다.

 

음의 가중치가 있게 되면 특성 구간을 계속 반복하면 시간이 줄어들 수 있게 됨으로 다른 방법을 사용해야 되지만 그런 경우가 조건에서 주어지지 않는다고 하기 때문에 무시하고 생각해도 상관 없는것이다.

 

따라서 모든 정점에서 다른 모든 정점으로의 최소 시간들을 구해주고 , 백트래킹 방식으로 정점을 하나씩 방문하면서 걸리는 최소시간을 구해주면 된다.

 

하지만 깡으로 다 구해버리면 시간초과가 날 수 있기 때문에 탐색을 하는 도중 이미 구해진 정답 보다 걸리는 시간이 커지게 되면 중단하는 방법으로 가지치기를 할 수 있다.

 

[소스 코드]

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int N, start_point;
int ans = 987654321;
vector<vector<int>> dt;
vector<bool> ck;

void calc(int cur, int sum, int depth)
{
	if (sum > ans) return;
	if (depth == N) { ans = sum; return; }

	for (int i = 0; i < N; i++)
	{
		if (i == cur) continue;
		if (ck[i]) continue;

		ck[i] = true;
		calc(i, sum + dt[cur][i], depth+1);
		ck[i] = false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> start_point;

	dt.resize(N);
	for (int i = 0; i < N; i++) dt[i].resize(N);
	ck.resize(N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> dt[i][j];

	for (int k = 0; k < N; k++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				dt[i][j] = min(dt[i][j], dt[i][k] + dt[k][j]);
			}
		}
	}

	ck[start_point] = true;
	calc(start_point, 0, 1);


	cout << ans;
	return 0;
}

 

굳