외판원 문제(TSP, 실버1)

1. 문제 설명

(1) 한 도시를 출발하여 모든 도시를 전부 한 번씩 방문한 뒤 시작 도시로 돌아올려고 한다.

 

(2) 이때 가능한 모든 경로 중 가장 짧은 경로의 길이는 얼마일까?

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 문제의 개수 C를 입력받는다.

 

(2) 두 번째 줄부터는 도시의 개수 N을 입력받는다.

( 2 <= N  && N <= 10 )

 

(3) 세 번째 줄부터는 N개 도시들 만큼 각 도시간의 거리를 입력한다.

 

출력 조건

(1) 모든 도시를 방문하면서 가장 짧은 경로의 길이를 출력한다. 

 

입력 예제

3
4
0 3 4 8
3 0 6 7
4 6 0 5
8 7 5 0
3
0 3 4
3 0 6
4 6 0
5
0 3 4 8 1
3 0 6 7 5
3 6 0 5 6
8 7 5 0 4
1 5 6 4 0

 

출력 예제

19
13
19

3. 기저 사례

(1) 모든 도시들을 다 방문했을 때는 다시 시작 도시로 돌아가고 종료한다.

 

 

 

4. 코드

public class TSP {    
    // 도시의 수
    static int N;
    
    // 각 도시간의 거리
    static int[][] dis;
    
    // 각 도시 방문 여부
    static boolean[] visited;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(sc.readLine());
        for(int i=0; i<C; i++) {
            N = Integer.parseInt(sc.readLine());
            dis = new int[N][N];
            visited = new boolean[N];
            
            // 각 도시간의 거리 입력
            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    dis[y][x] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append(shortestPath(new ArrayList<>(), 0)+"\n");
        }
        System.out.println(sb);
    }
    
    // 가장 최단 거리를 찾는 함수
    static int shortestPath(ArrayList<Integer> curCity, int curLength) {
        // 모든 도시를 방문한 경우
        if(curCity.size()==N) {
            return curLength+dis[curCity.get(0)][curCity.get(curCity.size()-1)];
        }
        
        // 초기 ret값을 비교할 수 없을 정도로
        // MAX_VALUE 값 설정
        int ret=Integer.MAX_VALUE;
        
        // 현재 도시 위치
        int here = curCity.isEmpty()?0:curCity.get(curCity.size()-1);
        
        // 재귀 호출 시작
        for(int next=0; next<N; next++) {
            if(!visited[next]){
                visited[next]=true;
                curCity.add(next);
                ret = Math.min(ret, shortestPath(curCity, curLength+dis[here][next]));
                visited[next]=false;
                curCity.remove(curCity.size()-1);
            }
        }
        return ret;
    }
}