[알고스팟] 여행하는 외판원1 :: 늦깎이 IT

[알고스팟 TSP1 URL]

1. 이 문제는 완전탐색으로 풀었습니다. N개의 도시가 있을 때, 출발 도시를 제외한 나머지 도시들을 방문하는

경우의 수는 (N-1)!입니다. 문제에서 N의 입력이 8이하이므로 완전탐색으로 풀어도 시간초과가 나지 않습니다.

2. 시작 도시를 정한 후, 그 도시로부터 순회를 시작합니다. 모든 도시를 돌았다면 최소 값을 갱신해줍니다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int C, N;
    public static double ans;
    public static double[][] map;
    public static boolean[] visited;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
 
        for (int t = 1; t <= C; t++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
 
            map = new double[N][N];
            visited = new boolean[N];
            ans = Double.MAX_VALUE;
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Double.parseDouble(st.nextToken());
                }
            }
 
            for (int i = 0; i < N; i++) {
                dfs(i, i, 0, 0.0);
            }
            System.out.println(ans);
 
        }
    }
 
    public static void dfs(int start, int end, int count, double totalCost) {
 
        if (count == N - 1) {
            ans = Math.min(ans, totalCost);
            return;
        }
        visited[start] = true;
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                dfs(i, end, count + 1, totalCost + map[start][i]);
            }
        }
        visited[start] = false;
 
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}