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

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

—

풀이

가능한 모든 경로! 고객들을 어느 순서로 먼저 방문하느냐에 따라서 값이 달라진다.
그러므로 순열로 풀어주면 된다.

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

public class Solution {
	static int n;
	static int[][] company,home,customers,result;
	static int MIN;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		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++) {
			n = Integer.parseInt(br.readLine());
			company = new int[1][2];
			home = new int[1][2];
			customers = new int[n][2];
			result = new int[n][2];
			StringTokenizer st = new StringTokenizer(br.readLine());
			isSelected = new boolean[n];
			MIN = Integer.MAX_VALUE;
   			//회사x,y값 
			company[0][0] = Integer.parseInt(st.nextToken());
			company[0][1] = Integer.parseInt(st.nextToken());
           		//집 x,y값
			home[0][0] = Integer.parseInt(st.nextToken());
			home[0][1] = Integer.parseInt(st.nextToken());
			//고객 x,y값
			for(int i=0; i<n; i++) {
				customers[i][0] =Integer.parseInt(st.nextToken());
				customers[i][1] =Integer.parseInt(st.nextToken());
			}			
			permutation(0);

			sb.append("#"+t+" "+MIN+"\n");
		}
		System.out.println(sb);
	}
	
	static void permutation(int cnt) {
		if(cnt == n) {
        		//처음 시작은 회사에서 시작
			int x = company[0][0];
			int y = company[0][1];
			int sum = Math.abs(company[0][0]-result[0][0])+Math.abs(company[0][1]-result[0][1]);
			for(int i=0; i<result.length-1; i++) {
            			//선택한 고객들 간의 거리
				sum += Math.abs(result[i][0]-result[i+1][0]) + Math.abs(result[i][1]-result[i+1][1]);
			}
            		//마지막 고객에서 집까지 가는 거리
			sum += Math.abs(result[result.length-1][0]-home[0][0])+Math.abs(result[result.length-1][1]-home[0][1]);

			MIN = Math.min(sum, MIN);		
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(isSelected[i]) continue;
			result[cnt][0] = customers[i][0];
			result[cnt][1] = customers[i][1];
			isSelected[i] = true;
			
			permutation(cnt+1);
			isSelected[i] = false;	
		}
	}

}