1247. [S/W 문제해결 응용] 3일차 - 최적 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD 

SW Expert Academy

 

1. 고객들 좌표를 배열에 저장(인덱스 : 0~ N-1)

ex) 고객이 3명이다.(0번고객, 1번고객, 2번고객)

2. 0,1,2 가지고 순열만듬

3. 그 순열을 result에 저장

4.result를 가지고 dfs //   result[depth] => 고객배열의 인덱스로 사용

5. 현재depth와 현재depth+1과 거리계산 -> 종료조건:depth==N-1

6. depth+1, 거리계산하면서 dfs재귀호출

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

public class Solution_1247_유동훈 {

	static int N;
	static boolean[] visit;
	static int[] result;
	static int answer = Integer.MAX_VALUE;
	static Custom arr[];
	static Custom home;
	static Custom company;
	
	static class Custom
	{
		int x;
		int y;
		
		public Custom(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	static void comb(int depth)
	{
		if(depth==N)
		{
			//System.out.println(Arrays.toString(result));
			//return result;
			dfs(0,0);
			return;
		}
		
		for(int i=0;i<N;++i)
		{
			if(!visit[i])
			{
				result[depth]=i;	//depth를 인덱스로 써라
				visit[i]=true;
				comb(depth+1);
				visit[i]=false;
			}
		}
		
		
	}
	
	static int distance(Custom now, Custom target)
	{
		
		return Math.abs(now.x-target.x)+Math.abs(now.y-target.y);
		
	}
	/*
	 * 현재위치 : x,y
	 */
	static void dfs(int depth, int distance)
	{
		if(depth==N-1)
		{
			distance=distance+distance(arr[result[depth]],home);
			answer=Math.min(answer, distance);
			return;
		}
		
		//초기화 : 회사~첫고객 거리계산
		if(depth==0 && distance==0) distance = distance + distance(company,arr[result[depth]]);
		
		//dfs(depth+1,distance(now,target));
		dfs(depth+1,distance+distance(arr[result[depth]],arr[result[depth+1]]));
	}
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T= Integer.parseInt(br.readLine());
		
		
		
		
		for(int test=1;test<=T;++test)
		{
			N=Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			company =new Custom(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			home =new Custom(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			arr = new Custom[N];
			for(int i=0;i<N;++i)
			{
				arr[i]=new Custom(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				
			}
			/*
			 * 
			 */
			//입력끝!
			
			
			visit= new boolean[N];
			result= new int[N];

			comb(0);
			
			System.out.println("#"+test+" "+answer);
			answer=Integer.MAX_VALUE;
		}
		

		
	}

	
}