[TSP1] Traveling Salesman Problem 1

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/TSP1

algospot.com :: TSP1

풀이입니다. 🤔

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;
    }
}

이 풀이는 기존에 풀었던 아래 문제와 유사합니다.

 

[PICNIC] 피크닉

완전탐색으로 도시를 방문하는 모든 순서에 따라 총 거리를 구한 뒤, 최소 값을 출력하도록 합니다. 
이 방법은 가장 비효율적이며 도시의 수가 적기 때문(최대 8개)에 가능한 방법입니다.

추 후 메모이제이션을 이용하여 더 빠르게 정답을 구할 수 있는 방법을 소개해보도록 하겠습니다.

 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️