[SWEA_1247 - JAVA] 최적 경로

풀이

이차원 배열을 만들지 않고 문제에 주어진 거리만을 구해서 풀이.
좌표를 편하게 관리하기 위한 customer 클래스.
permutation의 순서는 상관없기에 visit관리는 하지 않음.
순열로 index배열을 만들어 풀이 진행.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class customer {
    int row;
    int col;
 
    public customer(int row, int col) {
        super();
        this.row = row;
        this.col = col;
    }
 
}
 
public class Solution {
 
    static int N, min;
    static customer[] customers;
    static customer start;
    static customer end;
 
    // 순열 index
    static void nextPermutation(int[] set, int depth, int n, int k) {
        if (depth == k) { // 기저조건
            int s = solve(set); // 거리 계산
 
            min = min > s ? s : min; // 최저값 계산
            return;
        }
 
        for (int i = depth; i < n; i++) { // depth를 기준으로
            swap(set, i, depth); // 순열 위치 swap
            nextPermutation(set, depth + 1, n, k); // depth+1 재귀 호출
            swap(set, i, depth); // 원상 복구
        }
    }
 
    // swap
    static void swap(int[] set, int i, int index) {
        int temp = set[i];
        set[i] = set[index];
        set[index] = temp;
    }
 
    static int solve(int[] set) {
        int sum = 0;
        sum += getDistance(end, customers[set[0]]); // 회사부터의 거리
        for (int i = 0; i < set.length - 1; i++) {
            int idx = set[i]; // 순열 index 대입
            int next = set[i + 1]; // 순열 다음 index 대입
            sum += getDistance(customers[idx], customers[next]); // 고객끼리의 거리
        }
        sum += getDistance(customers[set[set.length - 1]], start); // 집으로부터의 거리
 
        return sum;
    }
 
    // 거리 계산
    static int getDistance(customer c1, customer c2) {
        return Math.abs(c1.row - c2.row) + Math.abs(c1.col - c2.col);
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int tc = Integer.parseInt(br.readLine());
 
        for (int test = 1; test <= tc; test++) {
            N = Integer.parseInt(br.readLine()); // 고객의 수
            customers = new customer[N]; // 고객의 위치 정보
            int[] set = new int[N]; // index 정보
            min = Integer.MAX_VALUE; // 최소 거리
 
            st = new StringTokenizer(br.readLine());
 
            // 시작 & 도착 위치 정보
            start = new customer(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            end = new customer(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
 
            // 고객 위치 정보 저장
            for (int i = 0; i < N; i++) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                customers[i] = new customer(x, y);
            }
 
            for (int i = 0; i < N; i++) {
                set[i] = i;
            }
 
            // =========================== 입력 ============================
            nextPermutation(set, 0, N, N);
 
            System.out.println("#" + test + " " + min);
 
        }
 
    }
 
}