반응형
TSP문제 이다. N의 범위가 10이하이므로 순열을 사용하여 풀었다.
perm라는 순열을 구하는 함수를 작성하였다. 여기서 arr라는 배열을 준비하여 각 인덱스 마다 도시의 번호로 지정하고, result라는 배열을 이용하여 도시들을 방문하는 경우의 수를 구하였다. result 배열이 전부 준비되었을 때 서로 도시끼리 갈 수 있는지 여부를 체크하면서 최종적으로 돌아오는 경우까지 계산하여 최종 답을 구하였다.
이 문제는 생각을 달리한다면 시간복잡도를 줄일 수 있는데, 그 경우는 시작 지점을 고정시키는 개념이다.
즉 0 1 2 3 4 0 과 1 2 3 4 0 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
87
88
89
|
package online.base;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_bj_10971_외판원순회2 {
static int N;
static int[][] map;
static int[] arr;
static int[] result;
static boolean[] visit;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N=Integer.parseInt(br.readLine());
map=new int[N][N];
result=new int[N];
visit=new boolean[N];
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++)
map[i][j]=Integer.parseInt(st.nextToken());
}
arr=new int[N];
for(int i=0;i<N;i++)
arr[i]=i;
answer=Integer.MAX_VALUE;
perm(0,0);
System.out.println(answer);
}
static void perm(int start,int depth) {
if(depth==N) {
if(result[0]!=0)
return;
//계산
int sum=0;
boolean find=true;
for(int i=0;i<N-1;i++) {
int index1=result[i];
int index2=result[i+1];
if(map[index1][index2]!=0)
sum+=map[index1][index2];
else {
find=false; break;
}
}
if(find) {
int index1=result[N-1];
int index2=result[0];
if(map[index1][index2]!=0)
sum+=map[index1][index2];
else
return;
answer= Math.min(answer, sum);
}
return;
}
for(int i=0;i<N;i++) {
if(visit[i]==false) {
visit[i]=true;
result[depth]=arr[i];
perm(i,depth+1);
visit[i]=false;
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
|
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
|
package online.base;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main_bj_10971_외판원순회2_2 {
static int N;
static int[][] map;
static boolean[] visit;
static int[] result;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N=Integer.parseInt(br.readLine());
map=new int[N][N];
visit=new boolean[N];
result=new int[N+1];
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
answer=Integer.MAX_VALUE;
visit[0]=true;
result[0]=0;
perm(0,1,0);
System.out.println(answer);
}
static void perm(int cur, int depth,int sum) {
if(depth==N) {
if(map[cur][0]==0)
return;
sum=sum+map[cur][0];
result[N]=0;
// System.out.println(Arrays.toString(result));
answer=Math.min(answer,sum);
return;
}
for(int i=1;i<N;i++) {
if(visit[i]==false && map[cur][i]!=0) {
visit[i]=true;
result[depth]=i;
perm(i,depth+1,sum+map[cur][i]);
visit[i]=false;
}
}
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 1197. 최소 스패닝 트리 (0) | 2020.04.09 |
|---|---|
| [SWEA] 1251. 하나로 (0) | 2020.04.09 |
| [BOJ] 10974. 모든 순열 (0) | 2020.04.07 |
| [BOJ] 2493. 탑 (0) | 2020.04.07 |
| [BOJ] 11559. Puyo Puyo (0) | 2020.04.06 |