[JAVA] 백준 10971

 

 

10971번: 외판원 순회 2

문제

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

풀이

방향이 있는 그래프에서 한 점에서 출발해서 모든 정점들을 돌고 자신의 정점으로 돌아오는 경우 중에서 최소값을 구하여라

📌 입력

for(int i=1; i<N; i++){
    String[] value = br.readLine().split(" ");
    for(int j=1; j<N; j++) {
        A[i][j] = Integer.parseInt(value[j-1].equals("0") ? INF+"" : value[j-1]);
    }
}

모든 배열에 값을 넣어주었고 만약 경로가 없는 경우 큰 수인 1_000_001을 넣었다.

📌 백트래킹

    public static void DFS(int depth, int value,int start, int now){
        if(value > min) return;
        if(depth == N-1){
            DFS(depth+1, value + A[now][start], start, start);
        }

        if(depth == N && start == now){
            min = value;
        }else{
            for(int i=1; i<N; i++){
                if(!V[i]){
                    V[i] = true;
                    DFS(depth+1, value+A[now][i], start, i);
                    V[i] = false;
                }
            }
        }

    }

모든 경로들을 탐색하면서 백트래킹 탐색을 진행한다.

• 만약 탐색을 하던 중 경로의 값이 발견된 최소값보다 커질경우 의미없는 경우의 수이기 때문에 탐색을 종료한다.
• 만약 depth가 정점의 수 -1일때 반드시 마지막 경로는 출발점이 되어야 하므로 출발지로 이동한다.

import java.io.*;

class Main {
    static int[][] A;
    static int N;
    static int min = Integer.MAX_VALUE;
    static boolean[] V;
    static int INF = 1_000_001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine())+1;
        V = new boolean[N];
        A = new int[N][N];

        for(int i=1; i<N; i++){
            String[] value = br.readLine().split(" ");
            for(int j=1; j<N; j++) {
                A[i][j] = Integer.parseInt(value[j-1].equals("0") ? INF+"" : value[j-1]);
            }
        }
        for(int i=1; i<N; i++){
            V[i] = true;
            DFS(1, 0, i, i);
            V[i] = false;
        }
        System.out.println(min);

    }

    public static void DFS(int depth, int value,int start, int now){
        if(value > min) return;
        if(depth == N-1){
            DFS(depth+1, value + A[now][start], start, start);
        }

        if(depth == N && start == now){
            min = value;
        }else{
            for(int i=1; i<N; i++){
                if(!V[i]){
                    V[i] = true;
                    DFS(depth+1, value+A[now][i], start, i);
                    V[i] = false;
                }
            }
        }

    }

}

결과