외판원 순회 2

📍 문제 설명

 

💡 접근

비용의 합을 구하는 DFS 문제, 마지막 합은 순회 지점의 합

1.1~N번 부터 출발할 수 있도록한다.

2.해당 출발지점에서 방문하지 않았고 갈 수 있는 N-1군데를 들르는 모든 경우의 수를 탐색한다.

3.N-1군데 모두 들렀으면 현재 지점에서 첫 지점으로 갈 수 있는지 확인 후 그 비용을 합한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, sum, answer = Integer.MAX_VALUE;
    static int[][] board;
    static char[] c;
    static int[] arr,pm;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        n = kb.nextInt();
        board = new int[n][n];
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //1~4번 부터 출발
        for(int i = 0; i < n; i++) {
            visited[i] = true;
            T.solution(0, 0, i, i);
            visited[i] = false;
        }
        System.out.println(answer);
    }

    private void solution(int L, int sum, int start, int idx) {
        //3군데 들리면 되고 다음 지점은 출발지점이다.
        if(L == n-1) {
            //순회할 수 있는 지점의 최솟값을 구해야한다.
            if(board[idx][start] != 0) {
                sum += board[idx][start];
                answer = Math.min(answer, sum);
            }
        }

        for(int i = 0; i < n; i++) {
            //현재 지점에서 i로 가는 비용이 0이면 갈 수 없다.
            if(board[idx][i] == 0) continue;
            //갈 곳이 방문한 곳이 아니면
            if (!visited[i]) {
                visited[i] = true;
                solution(L+1,  sum+board[idx][i], start, i);
                visited[i] = false;
            }
        }
    }

}