[Java SWEA 1247] 최적 경로

풀이

순열을 이용해서 풀었습니다.

문제에서도 전부다 순회하면 풀수있다고해서, 완전탐색 써야겠다구 생각했습니다.

 

순열을 사용해서 numbers배열에 customer_arr 인덱스 값을 넣었습니다. 

sum()내에서는 현재의 x,y값을 계속 바꿔가면서 거리계산을 했습니다.

package a0819;

import java.io.*;
import java.util.*;

class customer{
	int x;
	int y;
	public customer(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
}
public class Main {
	static int home_x,home_y,current_x,current_y,company_x,company_y, n;
	//customer 좌표 위치 저장용
	static ArrayList<customer> customer_arr; 
	//순열
	static boolean[] isSelected;
	static int[] numbers;
	//최종 값
	static int min_val;
	public static void main(String[] args) throws Exception{
		
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int tc=Integer.parseInt(br.readLine());
		StringBuilder sb=new StringBuilder();
		
		for(int t=1;t<=tc;t++) {
			min_val=Integer.MAX_VALUE;
			n=Integer.parseInt(br.readLine());
			numbers=new int[n];
			StringTokenizer st=new StringTokenizer(br.readLine()," ");
			isSelected=new boolean[n];
			customer_arr=new ArrayList<customer>();
			company_x=current_x=Integer.parseInt(st.nextToken());
			company_y=current_y=Integer.parseInt(st.nextToken());
			
			home_x=Integer.parseInt(st.nextToken());
			home_y=Integer.parseInt(st.nextToken());
 			for(int i=0;i<n;i++) {
				int x=Integer.parseInt(st.nextToken());
				int y=Integer.parseInt(st.nextToken());
				customer_arr.add(new customer(x,y));
			}
 			//순열 사용
			permutation(0);
			sb.append("#").append(t).append(" ").append(min_val).append("\n");
		}
		System.out.println(sb);
	}
	
	private static void permutation(int cnt) {
		// TODO Auto-generated method stub
		//기저 조건
		if(cnt==n) {
			
			sum();
			current_x=company_x;
			current_y=company_y;
			return;
		}
		for(int i=0;i<n;i++) {
			if(isSelected[i]) continue;
			
			numbers[cnt] = i;
			isSelected[i]=true;

			permutation(cnt+1);
			isSelected[i] =false;
		}
	}
	//numbers에 customer_arr의 인덱스 값을 저장하고, 값을 불러와서 거리계산. 
	private static void sum() {
		// TODO Auto-generated method stub
		int cnt=0;
		
		for(int i=0;i<n;i++) {
			//시간 단축하기 위해서 
			if(cnt>min_val) return;
			cnt+=Math.abs(current_x-customer_arr.get(numbers[i]).x) +Math.abs(current_y-customer_arr.get(numbers[i]).y);
			current_x=customer_arr.get(numbers[i]).x;
			current_y=customer_arr.get(numbers[i]).y;
		}
		cnt+=Math.abs(current_x-home_x)+Math.abs(current_y-home_y);
		min_val=Math.min(cnt, min_val);
	}

}

생각하는대 오래걸리고 막상 구현하는데는 어렵지않았던 문제...