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

1) 생각

도시들과 그 도시들간 이동할 때 발생하는 비용이 주어졌을 때, 외판원이 한 곳에서 출발해서 모든 도시를 돌고 다시 돌아왔을 때 최소의 비용을 구하라는 문제로 그리디적으로 접근 할 수도 있겠지만 항상 정답을 보장하는 것이 아니고 10개의 도시가 최대이므로 완전 탐색을 이용해서 답을 구해보았다.

2) 방안

한 번 방문한 도시는 출발할 때의 도시를 제외하고는 다시 방문해서는 안되므로 방문을 체크하는 배열을 만들고, DFS로 도시들을 방문하면서 방문한 도시를 방문체크 한 뒤 탐색을 진행한다.

이 때, Count 변수인 cnt의 체크와 함께 처음 시작한 곳으로 다시 돌아와주었는지도 체크함으로써 모든 곳을 방문하였는가가 아닌 순회를 하였는가를 체크해주었다.

이동하는 비용이 정해지면 이동중에 비용이 작아지는 경우는 없으므로 현재 최소 비용보다 크다면 그 방향의 탐색은 진행하지 않으므로써 시간을 줄였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.SocketTimeoutException;
import java.util.StringTokenizer;
 
public class Main{
    static int n;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[n];
        for(int i=0;i<n;i++) {
            start = i;
            solve(i,i,0,0);
        }
        System.out.println(min);
    }
    
    static int min = Integer.MAX_VALUE;
    static int start = 0;
    static boolean[] visited;
    private static void solve(int x,int y, int cnt,int sum) {
        if(cnt==n&&start==y) {
            min = Math.min(min, sum);
            return;
        }
        // 도착한 y에서 이동
        for(int i=0;i<n;i++) {
            if(visited[i]) continue;
            // y->i로 갈 수 없는 경우 0값을 가지고있다.
            // 따라서 y==i 일 경우만 체크해주면 틀린 값을 얻게된다.
            if(arr[y][i]==0) continue;
            if(sum+arr[y][i]>min) continue;
            visited[i] = true;
            solve(y,i,cnt+1,sum+arr[y][i]);
            visited[i] = false;
        }
    }
}