외판원 순회2

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{  
  
  static int N;
  static int[][] arr;
  static boolean[] visited;
  static int min = Integer.MAX_VALUE;
  static int start = 1;
  
  // 임의의 (1,1)도시를 하나씩 돌며 가중치를 더해가고 가중치 중 최소값을 찾는다.
  static void dfs(int city, int cnt, int cost) {
    
    // 기저조건 : 방문횟수가 N과 같을 때
    if(cnt == N && start != city && cost > 0 && arr[city][start] > 0) {
      // 탐방을 완료했을 경우
      // 시작점은 이미 방문 처리가 되었으므로 
      // 마지막 도시에서 처음 시작도시로의 가중치 값은 구해지지 않았다.
      // 별도로 구해준다.
      cost += arr[city][start];
      // 최종 구해진 거리 가중치 합산 값과 기존 합산값을 비교해 최소값을 넣어준다.
      min = Math.min(min, cost);
      return;
    } 
      
    // 각 도시를 방문한다. 즉 다음 방문할 도시를 뜻한다.
    for(int i=1; i<=N; i++) {
      if(arr[city][i] == 0) continue;  // 자기가 위치한 도시인 경우는 탐방불가
      if(visited[i]) continue;         // 이미방문한 도시면 탐방불가 
      
      visited[i] = true;
      dfs(i, cnt+1, cost+arr[city][i]);
      visited[i] = false;
    } 
    
  }
  
  // main
  public static void main(String[] args) throws Exception {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    
    N = Integer.parseInt(br.readLine());
    
    arr = new int[N+1][N+1];
    
    for(int i=1; i<=N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int j=1; j<=N; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
      } 
    } 
    
    visited = new boolean[N+1]; 
    for(int i=1; i<=N; i++) {
      visited[i] = true;
      dfs(i, 1, 0);  
    }
    
    
    bw.write(String.valueOf(min));
    br.close();
    bw.flush();
    bw.close();
  }
}