[ 백준 / 10971 ] 외판원 순회 2 ( 자바 )

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

DFS의 문제이다. DFS이므로 backtracking에 신경쓰도록 한다. 전형적인 느낌으로 모든 지점을 방문하면서 지나간다. 

무엇을 backtracking에 넣을 것인가?

각 방문했던 지점을 visited로 구분하는 것을 넣어준다. 이 부분만 신경써주면 된다.

sum은 매개변수에서 처리하기 때문에 따로 신경쓰지 않는다.

단, 중간에 거리가 0인 부분은 이동이 불가하므로 0을 만나면 그냥 return을 해준다.

 

//10971 외판원 순회2
import java.util.*;
public class Main {
	
	static int N;
	static int[][] array;
	static boolean visited[];
	static int answer=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		array = new int[N+1][N+1];
		visited = new boolean[N+1];
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				array[i][j] = sc.nextInt();
			}
		}
		
		for(int i=1;i<=N;i++) {
			visited[i]=true;
			DFS(i,i,0,0);
			visited[i]=false;
		}
		
		System.out.println(answer);
	}
	
	public static void DFS(int start, int now, int sum, int cnt) {
		if(cnt==N-1) {
			if(array[now][start]!=0) {
				sum += array[now][start];
				if(sum<answer) answer = sum;
			}
			return;
		}
		
		for(int i=1;i<=N;i++) {
			if(visited[i]==false && array[now][i]!=0) {
				visited[i]=true;
				DFS(start,i,sum+array[now][i],cnt+1);
				visited[i]=false;
			}
		}
	}

}