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
Posted by N'