[TSP1] Traveling Salesman Problem 1
개발이야기/알고스팟2022. 1. 4. 17:59
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/TSP1
algospot.com :: TSP1
Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를
www.algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.util.*;
public class Main {
private static final double[][] distances = new double[8][8];
private static final boolean[] visited = new boolean[8];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
int n = scanner.nextInt();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
distances[i][j] = scanner.nextDouble();
}
}
System.out.printf("%.10f\n", getMinVisitDistance(n));
Arrays.fill(visited, false);
}
}
private static double getMinVisitDistance(int n) {
double ret = Double.MAX_VALUE;
for (int i = 0; i < n; ++i) {
visited[i] = true;
ret = Math.min(ret, getMinVisitDistance(n, i, 1)); // 시작하는 도시마다, 총 방문거리가 달라질 수 있다.
visited[i] = false;
}
return ret;
}
private static double getMinVisitDistance(int n, int cur, int visitedCount) {
if (visitedCount >= n) return 0; // 기저사례 : 모든 도시를 방문
double ret = Double.MAX_VALUE;
for (int i = 0; i < n; ++i) {
if (cur == i) continue;
if (visited[i]) continue;
visited[i] = true;
ret = Math.min(ret, distances[cur][i] + getMinVisitDistance(n, i, visitedCount + 1));
visited[i] = false;
}
return ret;
}
}
|
cs |
이 풀이는 기존에 풀었던 아래 문제와 유사합니다.
[PICNIC] 피크닉
완전탐색으로 도시를 방문하는 모든 순서에 따라 총 거리를 구한 뒤, 최소 값을 출력하도록 합니다.
이 방법은 가장 비효율적이며 도시의 수가 적기 때문(최대 8개)에 가능한 방법입니다.
추 후 메모이제이션을 이용하여 더 빠르게 정답을 구할 수 있는 방법을 소개해보도록 하겠습니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
반응형
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [FIX] 문제 순서는 난이도 순이 아닙니다 (0) | 2022.01.05 |
|---|---|
| [CSBASEBALL] 각본 없는 야구 (0) | 2022.01.05 |
| [NQUEEN] N-Queen (0) | 2022.01.04 |
| [FIXPAREN] Mismatched Parenthesis (0) | 2022.01.04 |
| [BRACKETS2] Mismatched Brackets (0) | 2022.01.03 |