BOJ - 10971 ) 외판원 순회2

---

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

10971번: 외판원 순회 2

 

---

외판원순회(TSP)문제는 한지점에서 출발해 모든 노드를 거치고 다시 시작위치로 돌아오는 문제를 말한다.

 

그 중 최소 비용을 출력하는 것이 이번 외판원문제2이다.

 

백트래킹을 이용하여 미리구한값보다 크다면 더이상진행하지않는다.

 

문제에서도 알수 있듯이, MAP[I][J]값이 0이면 I->J로가는 경로가 없는 것이므로 진행할 수 없다.

 

 

---

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

public class TSP2 {
	public static int N , map[][] , answer = 987654321;
	public static boolean visit[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map= new int[N][N];
		visit = new boolean[N];
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j= 0 ; j < N ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i = 0 ; i <N ; i++) {
			visit[i] = true;
			dfs(i,0,i,0);
			visit[i] = false;
		}
		System.out.println(answer);
	}
	private static void dfs(int now, int cnt , int begin , int value) {
		if( value > answer) return;
		if(cnt == N-1 &&  map[now][begin] !=0) {
			// 모든 경우 순회
			answer = value + map[now][begin] > answer ? answer :value + map[now][begin] ;
			return;
		} 
		
		for(int i = 0 ; i < N ; i++) {
			 if(cnt < N-1 && i==begin) continue;
			 if(now == i) continue;
			 else if(!visit[i] && map[now][i] !=0) {
				visit[i] = true;
				dfs(i,cnt+1,begin,value+map[now][i]);
				visit[i] = false;
			}
		}
		
		
	}

}

---