예제 : 여행하는 외판원

어떤 나라에 n(2 <= n <= 10)개의 큰 도시가 있다.

한 영업사원이 한 도시에서 출발해서 다른 도시들을 전부 한번씩 방문한 뒤 돌아오려고 한다.

각 도시들은 모두 직선으로 연결되어 있다.

 

완전탐색을 이용해서 풀어보자.

무조건 0번도시에서 시작한다고 가정한다.

(n-1)개의 도시를 배열할 방법의 수는 (n-1)!이다.

package test;
 
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;
 
class Main{
    static int n;
    static int[][] dist;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        
        dist = new int[n][n];
        
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                int input = scanner.nextInt();
                dist[i][j] = input;
            }
        }
        
        ArrayList<Boolean> visited = new ArrayList<Boolean>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        visited.add(true); // 0은 방문했다고 표시해 준다.
        for(int i = 1; i < n; ++i) {
            visited.add(false);
        }
        path.add(0); //처음 시작 도시는 0 이다.
        
        System.out.println(shortestPath(visited, path, 0));
        
//        for(int i = 0; i < n; i ++) {
//            for(int j : dist[i]) {
//                System.out.print(j + " ");
//            }    
//            System.out.println();
//        }
        
    }
    public static double shortestPath(ArrayList<Boolean> visited, ArrayList<Integer> path, int currentLength) {
        if(path.size()==n) {
            for(int i : path) {
                System.out.print(i + " ");
            }
            System.out.println(currentLength+dist[path.get(path.size()-1)][path.get(0)]);
            
            // 재귀함수로 마지막까지 가는 루트를 구한 다음 마지막에서 처음으로 돌아가는 비용을 더해준다.
            return currentLength+dist[path.get(path.size()-1)][path.get(0)]; 
        }
        
        double ret = 1.797679e+308;
        double cand = 0;
        for(int next = 0; next < n; ++next) {
            if(visited.get(next)) {
                continue;
            }
            int here = path.get(path.size()-1); // path = {0,};
            path.add(next);
            visited.set(next, true);
//            System.out.println("====================================");
//            System.out.println("here : " + here +" next : " + next);
//            for(int i : path) {
//                System.out.println("path = " + i);
//            }
//            for(Boolean i : visited) {
//                System.out.println("visited = " + i);
//            }
//            System.out.println("cost : " + dist[here][path.size()-1]);
//            path = {0, 1} , visited = {true, true}
            cand = shortestPath(visited, path, currentLength+dist[here][next]);
            
            ret = Math.min(ret, cand);
//            System.out.println("ret : " + ret);
            visited.set(next, false);
            path.remove(path.size()-1);
//            for(int i : path) {
//                System.out.println("after path = " + i);
//            }
//            for(Boolean i : visited) {
//                System.out.println("after visited = " + i);
//            }
        }
        return ret;
    }
}

 

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
 
4
0 20 28 30
25 0 27 28
30 35 0 29
280 29 27 0
 
main
path : 0
visited : true
 
short1
//s1 for next = 1
next = 1
path : 0 1
visited : true true
    //s2 for next = 2
    short2
    next = 2
    path : 0 1 2
    visited : true true true
        short3
        next = 3
        path : 0 1 2 3
        visited : true true true true
            short4
            조건 path.size() == n
            return s4;
        s3 = Math.min(ret, s4);
        path : 0 1 2
        visited : true true true false
        return s3;
    s2 = Math.min(ret, s3);
    path : 0 1
    visited : true true false false
    
    //s2 for next = 3
    next = 3
    path : 0 1 3
    visited : true ture false true
        short3
        next = 2
        path : 0 1 3 2
        visited : true true true true
            short4
            조건 path.size() == n
            return s4;
        s3 = Math.min(ret, s4);
        path : 0 1 3
        visited : true true false true
        return s3;
    s2 = Math.min(ret, s3);
    path : 0 1
    visited : true true
    return s2;    
s1 = Math.min(s2, ret);
path : 0
visited : true false false false
 
//s1 for next = 2
next = 2
path : 0 2 
visited : true false true false
    short2
    next = 1
    path : 0 2 1
    visited : true true true false
        short3
        next = 3
        path : 0 2 1 3
...