[SWEX] 최적의 경로(1247번, 자바)

 

 

DFS 이용!!

 

visit : 방문 확인 

distance[num]: num번 손님까지 방문했을 때의 거리 

loc[x][0], loc[x][1]: 위치 좌표

 

 

import java.util.*;


class Solution
{
	
	static int N;
	static int[][] loc;
	static boolean[] visit;
	static int[] distance;
	static int answer=0;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();
	
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			answer=Integer.MAX_VALUE;
			N=sc.nextInt();
			loc=new int[N+2][N+2];
			visit=new boolean[N+2];
			distance=new int[N+2];
			
			for(int i=0;i<N+2;i++) {
				loc[i][0]=sc.nextInt();
				loc[i][1]=sc.nextInt();
			}
			
			dfs(0,0);
			System.out.println("#"+test_case+" "+answer);
	}
		
	
	}
	
	static void dfs(int num, int count) {
		if(count>=N) {
			System.out.println(distance[num]);
			answer=Math.min(answer, distance[num]+Math.abs(loc[num][0]-loc[1][0])+Math.abs(loc[num][1]-loc[1][1]));
			return;
		}
		
		for(int i=2;i<N+2;i++) {
			if(visit[i]) continue;
			
			distance[i]=Math.abs(loc[num][0]-loc[i][0])+Math.abs(loc[num][1]-loc[i][1])+distance[num];
			visit[i]=true;
			
			dfs(i,count+1);
			distance[i]=0;
			visit[i]=false;
		}
	}
}