SWEA1247 최적 경로

문제에서 친절하게 모든 경로를 살펴도 좋다고 말해주고 있다.

또, 최대 10명의 고객 좌표가 주어지기 때문에 순열을 사용하면 된다는 걸 알 수 있다.

인접행렬을 이용해 고객 간 이동거리를 배열에 담아두고 활용한다.

그리고 순열의 매개변수로 최소 거리를 계산하면서 지금까지 더해진 거리가 이미 최소거리보다 길어졌다면 더이상 계산하지 않음으로써 불필요한 연산을 하지 않을 수 있다.

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


public class Solution {
	static int N, minofDist = Integer.MAX_VALUE;
	static int[] company = new int[2];
	static int[] home = new int[2], numbers;
	static int[][] customer, matrix;
	static boolean[] isSelected;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	public static void makeAdMatrix() {
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				int dist = Math.abs(customer[i][0] - customer[j][0]) + Math.abs(customer[i][1] - customer[j][1]);
				matrix[i][j] = dist;
				matrix[j][i] = dist;
			}
		}
		for(int i = 0; i < N; i++) {
			int dist_home = Math.abs(customer[i][0] - home[0]) + Math.abs(customer[i][1] - home[1]);
			int dist_company = Math.abs(customer[i][0] - company[0]) + Math.abs(customer[i][1] - company[1]);
			matrix[i][N] = dist_home;
			matrix[N][i] = dist_home;
			matrix[i][N + 1] = dist_company;
			matrix[N + 1][i] = dist_company;
		}
	}
	public static void Permutation(int cnt, int dist, int preLoca) {
		if(cnt == N) {
			dist += matrix[N][preLoca];
			if(dist < minofDist) minofDist = dist;
			return;
		}	
		if(dist > minofDist) return;
		for(int i = 0; i < N; i++) {
			if(isSelected[i]) {
				continue;
			}
			int add_dist = matrix[preLoca][i];
			isSelected[i] = true;
			Permutation(cnt + 1, dist + add_dist, i);
			isSelected[i] = false;
		}
	}
	public static void main(String[] args) throws IOException {
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			minofDist = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			customer = new int[N][2];
			st = new StringTokenizer(br.readLine(), " ");
			company[0] = Integer.parseInt(st.nextToken());
			company[1] = Integer.parseInt(st.nextToken());
			home[0] = Integer.parseInt(st.nextToken());
			home[1] = Integer.parseInt(st.nextToken());
			for (int i = 0; i < N; i++) {
				customer[i][0] = Integer.parseInt(st.nextToken());
				customer[i][1] = Integer.parseInt(st.nextToken());
			}
			matrix = new int[N + 2][N + 2]; // +2는 집, 회사와의 거리.
			makeAdMatrix();
			
			numbers = new int[N];
			isSelected = new boolean[N];
			Permutation(0, 0, N + 1);
			bw.append("#" + tc + " " + minofDist + "\n");
		}
		bw.flush();
	}
}