SWEA - 1247 : 최적 경로 [자바]

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

public class Solution {
	static int N, result;
	static boolean v[];
	static int[] cstm, company, home;
	static int[][] customer;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine()); // 테스트케이스 개수

		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine()); // 고객의 수

			StringTokenizer st = new StringTokenizer(br.readLine());
			company = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
			home = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };

			customer = new int[N][2];
			for (int i = 0; i < N; i++) {
				customer[i][0] = Integer.parseInt(st.nextToken());
				customer[i][1] = Integer.parseInt(st.nextToken());
			}

			cstm = new int[N];
			v = new boolean[N];
			result = Integer.MAX_VALUE;
			perm(0);
			sb.append("#").append(test_case).append(" ").append(result).append("\n");
		}
		System.out.println(sb);
		br.close();
	}

	static void perm(int cnt) {
		if (cnt == N) { // N명 나열 했으면
			int sum = 0;
			for (int i = 0; i < N-1; i++) {
				int k = cstm[i]; // 고객 번호
				int kn = cstm[i + 1];
				sum += Math.abs(customer[k][0] - customer[kn][0]) + Math.abs(customer[k][1] - customer[kn][1]);
			}
			sum += Math.abs(company[0] - customer[cstm[0]][0]) + Math.abs(company[1] - customer[cstm[0]][1]);
			sum += Math.abs(home[0] - customer[cstm[N - 1]][0]) + Math.abs(home[1] - customer[cstm[N - 1]][1]);
			result = Math.min(sum, result);
			return;
		}

		for (int i = 0; i < N; i++) {
			if (v[i])
				continue;
			v[i] = true;

			cstm[cnt] = i;
			v[i] = true;
			perm(cnt + 1);
			v[i] = false;
		}
	}

}