17182번: 우주 탐사선

문제 설명

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

17182번: 우주 탐사선

[문제]

 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 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]

3 0
0 30 1
1 0 29
28 1 0

[예제 출력 1]

2

[예제 입력 2]

4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

[예제 출력 2]

74

---

풀이

 문제에서 요구하는 바는 모든 행성을 도는 데 최소 시간인데, 각 행성을 한 번씩만 방문하는 것이 아닌 중복 방문을 하더라도 걸리는 시간을 최소로 걸려야 하기 때문에 단순히 최소 시간만을 구하는 최단 경로 구하기나 최소 스패닝 트리와는 약간 문제 해결이 다르다.

 우선적으로 필요한 것은 두 행성 간 최소 시간이기 때문에 이를 플로이드 - 와샬 알고리즘을 통해 값을 구한다. 이후 구해진 값들을 바탕으로 완전 탐색을 진행해도 되지만, 앞선 플로이드 - 와샬 속 경로 갱신 과정을 좀 더 문제 해결에 사용하고자 해당 경로를 지나는데 방문한 행성들을 저장하는 변수를 만들어 사용했다.

 비트 마스킹을 통해 행성들의 방문을 체크하여, 플로이드 - 와샬 알고리즘 도중 거리를 갱신하는 과정에서 해당 최단 거리 값이 지나는 행성이 어디인지도 저장을 한다. 이후 재귀 호출 함수를 통해 탐색을 진행하는데, 현재 행성 기준으로 방문하지 않은 행성을 택하는 과정에서 해당 최단 경로 속 방문 비트를 통해 다른 추가적인 행성들도 중복 처리를 한다.

 이를 통해 단순히 해당 행성으로 가는 경로를 고르는 것 뿐만 아니라 이 최단 경로에 속한 다른 행성들도 추가로 방문 처리가 가능하여, 탐색에 걸리는 시간을 줄일 수 있다.

 이러한 알고리즘으로 완전 탐색 함수를 돌려, 모든 행성을 방문 했을 때 기존 정답과 비교해 최소값을 택하는 과정을 반복한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int times[10][10];
int visitedPath[10][10] = { 0, };
int N, K;

void search(int now, int acc, int visitedBits, int& answer) {
	if (visitedBits == (1 << N) - 1) {//모든 행성 방문 완료
		answer = min(answer, acc);//값 비교
		return;
	}
	
	for (int i = 0; i < N; i++) {
		if ((visitedBits & (1 << i)) == 0) {//방문하지 않은 행성인 경우
			search(i, acc + times[now][i], visitedBits | visitedPath[now][i], answer);
		}
	}
}

int main() {
	int temp, answer = 987654321;

	cin >> N >> K;

	for (int i = 0; i < N; i++) {//이동 시간과 경로 비트 초기화
		for (int j = 0; j < N; j++) {
			cin >> temp;
			times[i][j] = temp;
			visitedPath[i][j] = (1 << i) | (1 << j);
		}
	}

	for (int k = 0; k < N; k++) //플로이드- 와샬 알고리즘 사용
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (times[i][j] > times[i][k] + times[k][j]) {//단순 거리 최신화에 방문 행성도 표시
					times[i][j] = times[i][k] + times[k][j];
					visitedPath[i][j] = visitedPath[i][k] | visitedPath[k][j];
				}

	search(K, 0, 0, answer);

	cout << answer;

	return 0;
}

---

결과