문제 >> 1247. [S/W 문제해결 응용] 3일차 - 최적 경로
Permutation 알고리즘을 이용해 고객의 집에 대한 모든 순서를 먼저 만든다 (index 이용)
각각의 경우에 대해 거리를 계산하고, 최소값을 갱신한다.
최소값을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class pair {
int y;
int x;
public pair(int y, int x) {
this.y = y;
this.x = x;
}
}
public class Solution1247 {
static pair home;
static pair company;
static pair[] cus;
static int ans = Integer.MAX_VALUE;
public static int getDistance(pair p1, pair p2) {
return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
}
public 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(company, cus[set[0]]);
for(int i=0;i<set.length-1;i++) {
int idx = set[i];
int next = set[i+1];
sum+= getDistance(cus[idx], cus[next]);
}
sum+=getDistance(cus[set[set.length-1]], home);
return sum;
}
public static void perm(int[] set, int size, int n, int k) {
if (size == k) { //종료조건
int s = solve(set);
ans = ans > s? s: ans;
return;
}
for (int i = size; i < n; i++) {
swap(set, i, size);
perm(set, size + 1, n, k);
swap(set, i, size);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= TC; tc++) {
int N = Integer.parseInt(br.readLine()); // 고객 수
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
ans = Integer.MAX_VALUE;
int[] set = new int[N];
company = new pair(y, x);
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
home = new pair(y, x);
cus = new pair[N];
for (int i = 0; i < N; i++) {
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
cus[i] = new pair(y, x);
}
for (int i = 0; i < N; i++) {
set[i] = i;
}
perm(set, 0, N, N);
System.out.println("#"+tc + " "+ans);
}
}
}
|
cs |
'Algorithm Problem Solving' 카테고리의 다른 글
| [SWEA] 2819 격자판의 숫자 이어 붙이기 (0) | 2019.02.16 |
|---|---|
| [BOJ] 9999 : 구구 **결정적 힌트** (5) | 2019.02.13 |
| [SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (2) | 2019.02.12 |
| [BOJ] 10819 : 차이를 최대로 (0) | 2019.02.08 |
| [BOJ] 1987 : 알파벳 (0) | 2019.02.08 |