반응형
어떤 나라에 n(2 <= n <= 10)개의 큰 도시가 있다.
한 영업사원이 한 도시에서 출발해서 다른 도시들을 전부 한번씩 방문한 뒤 돌아오려고 한다.
각 도시들은 모두 직선으로 연결되어 있다.
완전탐색을 이용해서 풀어보자.
무조건 0번도시에서 시작한다고 가정한다.
(n-1)개의 도시를 배열할 방법의 수는 (n-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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | package test; import java.util.ArrayList; import java.util.Scanner; import java.util.Vector; class Main{ static int n; static int[][] dist; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); dist = new int[n][n]; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { int input = scanner.nextInt(); dist[i][j] = input; } } ArrayList<Boolean> visited = new ArrayList<Boolean>(); ArrayList<Integer> path = new ArrayList<Integer>(); visited.add(true); // 0은 방문했다고 표시해 준다. for(int i = 1; i < n; ++i) { visited.add(false); } path.add(0); //처음 시작 도시는 0 이다. System.out.println(shortestPath(visited, path, 0)); // for(int i = 0; i < n; i ++) { // for(int j : dist[i]) { // System.out.print(j + " "); // } // System.out.println(); // } } public static double shortestPath(ArrayList<Boolean> visited, ArrayList<Integer> path, int currentLength) { if(path.size()==n) { for(int i : path) { System.out.print(i + " "); } System.out.println(currentLength+dist[path.get(path.size()-1)][path.get(0)]); // 재귀함수로 마지막까지 가는 루트를 구한 다음 마지막에서 처음으로 돌아가는 비용을 더해준다. return currentLength+dist[path.get(path.size()-1)][path.get(0)]; } double ret = 1.797679e+308; double cand = 0; for(int next = 0; next < n; ++next) { if(visited.get(next)) { continue; } int here = path.get(path.size()-1); // path = {0,}; path.add(next); visited.set(next, true); // System.out.println("===================================="); // System.out.println("here : " + here +" next : " + next); // for(int i : path) { // System.out.println("path = " + i); // } // for(Boolean i : visited) { // System.out.println("visited = " + i); // } // System.out.println("cost : " + dist[here][path.size()-1]); // path = {0, 1} , visited = {true, true} cand = shortestPath(visited, path, currentLength+dist[here][next]); ret = Math.min(ret, cand); // System.out.println("ret : " + ret); visited.set(next, false); path.remove(path.size()-1); // for(int i : path) { // System.out.println("after path = " + i); // } // for(Boolean i : visited) { // System.out.println("after visited = " + i); // } } return ret; } } | cs |
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
|
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
4
0 20 28 30
25 0 27 28
30 35 0 29
280 29 27 0
main
path : 0
visited : true
short1
//s1 for next = 1
next = 1
path : 0 1
visited : true true
//s2 for next = 2
short2
next = 2
path : 0 1 2
visited : true true true
short3
next = 3
path : 0 1 2 3
visited : true true true true
short4
조건 path.size() == n
return s4;
s3 = Math.min(ret, s4);
path : 0 1 2
visited : true true true false
return s3;
s2 = Math.min(ret, s3);
path : 0 1
visited : true true false false
//s2 for next = 3
next = 3
path : 0 1 3
visited : true ture false true
short3
next = 2
path : 0 1 3 2
visited : true true true true
short4
조건 path.size() == n
return s4;
s3 = Math.min(ret, s4);
path : 0 1 3
visited : true true false true
return s3;
s2 = Math.min(ret, s3);
path : 0 1
visited : true true
return s2;
s1 = Math.min(s2, ret);
path : 0
visited : true false false false
//s1 for next = 2
next = 2
path : 0 2
visited : true false true false
short2
next = 1
path : 0 2 1
visited : true true true false
short3
next = 3
path : 0 2 1 3
...
|
cs |
반응형
'알고리즘 > 알고리즘 문제해결전략' 카테고리의 다른 글
예제 : 수열의 빠른 합 (0) | 2020.11.23 |
---|---|
문제 ID : CLOCKSYNC, 난이도: 중 (0) | 2020.11.23 |
문제 ID : BOARDCOVER , 난이도: 하 (0) | 2020.11.04 |
문제 ID : PICNIC, 난이도: 하 (0) | 2020.11.02 |