[SWEA] 1247 최적경로

 

방문해야할 곳은 회사 - N개의 고객 - 집 이렇게 12개다

그럼 회사와 집은 고정시켜두고 N개를 next_permutation을 통해 확인하면 된다

 

10!이기 때문에 시간은 충분하게 나온다!

 

소스코드 ( Java)

import java.util.Scanner;
 
public class Solution {
    public static int[] order = new int[10];
    public static int[][] arr = new int[10][2];
    public static int ox,oy,hx,hy,n,ans;
    public static int dist(int x1,int y1,int x2,int y2) {
        return(Math.abs(x1-x2)+Math.abs(y1-y2));
    }
    public static void swap(int x,int y) {
        int temp = order[x];
        order[x]=order[y];
        order[y]=temp;
    }
    public static int number() {
        int ret = dist(ox,oy,arr[order[0]][0],arr[order[0]][1]);
        for (int i = 0; i < n-1; i++) ret += dist(arr[order[i]][0], arr[order[i]][1], arr[order[i + 1]][0], arr[order[i + 1]][1]);
        ret += dist(arr[order[n - 1]][0], arr[order[n - 1]][1], hx, hy);
        return ret;
    }
    public static void solve(int now) {
        if(now==n-1) {
            ans = Math.min(ans, number());
            return;
        }
        for(int i=now;i<n;i++) {
            swap(i,now);
            solve(now+1);
            swap(i,now);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        for(int tc=1;tc<=t;tc++) {
            n = sc.nextInt();
            for(int i=0;i<n;i++) order[i]=i;
            ox=sc.nextInt(); oy=sc.nextInt();
            hx=sc.nextInt(); hy=sc.nextInt();
            for(int i=0;i<n;i++) {
                arr[i][0]=sc.nextInt();
                arr[i][1]=sc.nextInt();
            }
            
            ans = Integer.MAX_VALUE;
            solve(0);
            System.out.println("#"+tc+" "+ans);
        }
    }
}
 

 

소스코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int order[10];
int arr[10][2];
int officeX, officeY, houseX, houseY;
 
int dist(int x1, int y1, int x2, int y2) {
    return(abs(x1 - x2) + abs(y1 - y2));
}
int main() {
    int t; scanf(" %d", &t);
    for (int tc = 1; tc <= t; tc++) {
        int n; scanf(" %d", &n);
        for (int i = 0; i < n; i++) order[i] = i;
        scanf("%d %d %d %d", &officeX, &officeY, &houseX, &houseY);
        for (int i = 0; i < n; i++) scanf(" %d %d", &arr[i][0], &arr[i][1]);
 
        int ans = 1e9;
        do {
            int temp = dist(officeX, officeY, arr[order[0]][0], arr[order[0]][1]);
            for (int i = 0; i < n-1; i++) temp += dist(arr[order[i]][0], arr[order[i]][1], arr[order[i + 1]][0], arr[order[i + 1]][1]);
            temp += dist(arr[order[n - 1]][0], arr[order[n - 1]][1], houseX, houseY);
            ans = min(ans, temp);
        } while (next_permutation(order,order+n));
        printf("#%d %d\n", tc, ans);
    }
}