외판원 순회 2 (10971번)
https://www.acmicpc.net/problem/6603
이전풀이
- 처음에는 모든 순열을 구해서
ArrayList에 저장하고 그 순열을 이용해 최소값을 구하도록 구혔했었다. 그러다보니 속도에서 700ms 이상의 퍼포먼스가 나왔고 아래와 같은 방법으로 수정한 결과 300ms대 퍼포먼스가 나왔다. 그러나 다른 사람들의 풀이를 보면DP를 이용한 풀이가 속도면에서 우월했다. DP또는 코드를 개선해 개선할 필요가 있다.
풀이방법
- 순열을 구할 때마다 최소값을 계산하는 방식으로 구현하였다.
- 원래의 도시로 다시 돌아와야 하므로
1, 2, 3, 4로 순회할 경우1, 2, 3, 4, 1로 수정한 후 계산했다.
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
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] result = null;
private static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
result = new int[N+1];
StringTokenizer st = null;
int[] arr = new int[N];
boolean[] visited = new boolean[N];
for(int i=0; i<N; i++) {
arr[i] = i+1;
}
int[][] W = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
solve(arr, W, visited, N, 0);
System.out.println(min);
}
private static void calculate(int[][] W, int[] tmp) {
boolean canMove = true;
int sum = 0;
for(int j=0; j<tmp.length-1; j++) {
if (W[tmp[j]][tmp[j+1]] == 0) {
canMove = false;
}
sum += W[tmp[j]][tmp[j+1]];
}
if (canMove) {
min = Math.min(min, sum);
}
}
private static void solve(int[] arr, int[][] W, boolean[] visited, int r, int c) {
if (c == r) {
result[arr.length] = result[0];
calculate(W, result);
}
else {
for(int i=0; i<arr.length; i++) {
if (!visited[i]) {
visited[i] = true;
result[c] = arr[i];
solve(arr, W, visited, r, c+1);
visited[i] = false;
}
}
}
}
}
Comments powered by Disqus.