[백준] 10971 외판원 순회 2 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class TSP {
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int[][] W;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        input();
        solve();
        System.out.println(ans);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        W = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static void solve() {
        for(int i = 0; i < N; i++) {
            boolean[] checked = new boolean[N];
            dfs(i,i,0, checked);
        }
    }

    public static void dfs(int s, int c, int sum, boolean[] checked) {
        //한바퀴 돌았을 때
        if(checked[c] && s == c) {
            //모든 도시를 방문했는지 체크해야함
            for(int i = 0; i < N; i++) {
                if(!checked[i]) return;
            }
            //모든 도시를 방문했다면 맞게 돈것이므로 ans와 sum을 비교해서 적은 값을 ans에 넣음
            ans = Math.min(ans, sum);
        }
        //현재 위치가 출발 지점은 아니고 방문한 도시일 때 return
        if(checked[c]) return;

        checked[c] = true;
        for(int i = 0; i < N; i++) {
            if(W[c][i] != 0) dfs(s, i, sum+W[c][i], checked);
        }
        checked[c] = false;
    }
}

DFS + 백트래킹 문제였다. 인접리스트로 바꿔서 풀면 좀 더 쉬웠을꺼 같은데 그냥 주어진대로 인접행렬로 풀었다.

 

dfs 함수에 필요했던 매개변수 : 출발 지점을 저장하는 변수 s, 현재 위치를 저장하는 변수 c, 현재위치 까지 오는데 드는 총 비용 sum, 방문기록을 저장하는 checked[] 

 

종료조건은 두가지이다. 시작지점으로 돌아온 경우와 시작지점은 아니지만 이미 방문한 지점을 방문한 경우이다.

 

만약 시작지점으로 돌아온 경우는 모든 도시를 돌았는지 검사해야 함으로 checked[] 배열을 돌면서 확인해준다.

모든 도시를 방문했을 경우는 현재 최솟값과 비교하여 더 작을 경우 값을 업데이트 해준다.

 

두 번째 종료조건은 checked[] 배열을 확인해서 이미 방문했을 경우는 바로 return 해주면 된다.

 

그리고 순열 문제와 비슷하게 모든 경우의 수를 돌아야 하므로 재귀적으로 갈 수 있는 좌표만 방문해주면 된다.