[알고리즘] 최적 경로

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

SW Expert Academy

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	static int[] array;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; testCase++) {
			int N = Integer.parseInt(br.readLine());
			
			int[][] map = new int[N][N]; 
			st = new StringTokenizer(br.readLine());
			Point company = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			Point home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			Point[] points = new Point[N]; 
			array = new int[N];
			for (int i = 0; i < N; i++) {
				array[i] = i;
			}
			for (int i = 0; i < N; i++) {
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				points[i] = new Point(x, y);
			}
			
			int minDistance = Integer.MAX_VALUE;
			do {
				Point curPoint = company;
				int distance = 0;
				for (int i = 0; i < N; i++) {
					Point nextPoint = points[array[i]];
					distance += Math.abs(curPoint.x - nextPoint.x) + Math.abs(curPoint.y - nextPoint.y);
					curPoint = nextPoint;
				}
				Point end = home;
				distance += Math.abs(curPoint.x - end.x) + Math.abs(curPoint.y - end.y);
				
				minDistance = Math.min(minDistance, distance);
			} while (np());
			sb.append("#").append(testCase).append(" ").append(minDistance).append("\n");
		}
		System.out.println(sb);
	}

	private static boolean np() {
		int i = array.length - 1;
		while (i > 0 && array[i-1] >= array[i]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = array.length - 1;
		while (array[i-1] >= array[j]) {
			j--;
		}
		int temp = array[i-1];
		array[i-1] = array[j];
		array[j] = temp;
		Arrays.sort(array, i, array.length);
		return true;
	}
}

나의 풀이

- 완전탐색으로 np를 활용하면 된다.