SW Expert Academy - 1247번(최적 경로)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD

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

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine()); // 테케 갯수

        StringBuilder sb = new StringBuilder();
        int problemNum = 1;

        while (T-- > 0) {
            int N = Integer.parseInt(reader.readLine()); // 고객의 수
            int[][] value = new int[N + 2][2];
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int i = 0; i < N + 2; i++) {
                for (int j = 0; j < 2; j++) {
                    value[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
            }

            int min = Integer.MAX_VALUE;

            int[] index = new int[N];
            for (int i = 0; i < N; i++) {
                index[i] = i + 2;
            }

            do {
                // 출발은 회사
                // 도착은 집
                int sum = 0;

                // 회사에서 첫 번째 고객까지의 거리
                sum += Math.abs(value[index[0]][0] - value[1][0]) + Math.abs(value[index[0]][1] - value[1][1]);

                for (int i = 1; i < index.length; i++) {
                    sum += Math.abs(value[index[i]][0] - value[index[i - 1]][0]) + Math.abs(value[index[i]][1] - value[index[i - 1]][1]);
                    if (sum > min) break;
                }

                // 마지막 고객에서 집까지의 거리
                sum += Math.abs(value[index[index.length - 1]][0] - value[0][0]) + Math.abs(value[index[index.length - 1]][1] - value[0][1]);

                min = Math.min(min, sum);
            } while (np(index));

            sb.append("#").append(problemNum++).append(" ");
            sb.append(min).append("\n");
        }

        System.out.println(sb);
    }

    private static boolean np(int[] arr) {
        int lastIndex = arr.length - 1;

        int i = lastIndex;
        while (i > 0 && arr[i - 1] >= arr[i]) i--; // arr[i - 1] < arr[i]가 되면 탈출한다.

        if (i == 0) return false; // 내림차순으로 정렬이 다 된 경우

        int j = lastIndex;
        while (arr[i - 1] >= arr[j]) j--; // arr[i - 1] < arr[j]가 되면 탈출한다.

        swap(arr, i - 1, j);

        int k = lastIndex;
        while (i < k) swap(arr, i++, k--);

        return true;
    }

    private static void swap(int[] arr, int from, int to) {
        int temp = arr[from];
        arr[from] = arr[to];
        arr[to] = temp;
    }
    
}

• 회사와 집, 고객들의 거리 정보를 담은 배열을 만든다.
• 회사와 집의 순서는 고정이므로, 사이 고객들의 거리를 순열을 통해 모든 경우의 수를 만들고 처음과 끝에 회사와 집까지의 거리를 더하여 최솟값을 찾는다.
• 가지치기를 통해 백트래킹을 사용할 수 있으나 마땅한 방법이 생각나지 않아 시간이 줄어들지 않았다...😥