https://www.acmicpc.net/problem/10971
10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.
www.acmicpc.net
앞에서 next_permutation을 사용해서 풀었는데 dfs를 사용해서도 풀어봤다.
개인적으로 아직 넥퍼뮤가 익숙하지 않아서 dfs로 푸는 게 더 풀기 쉬웠다.
dfs를 사용할때는 방문 표시를 잘해주면 된다.
현재 도시를 방문하는 경우 check배열을 true값으로 바꿔주고 현재 도시를 선택하는 경우를 모두 해준 경우(탐색에서 돌아온 경우)
방문 표시를 지워준다(false 값으로 바꿔준다)
자세한 설명은 아래 코드를 참고!
|
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
|
#include <iostream>
using namespace std;
int w[10][10];
int n;
int ans;
void dfs(int index,int cnt, int sum, bool check[]) {
//첫번째 도시부터 마지막 도시까지 방문했으면
if(cnt == n-1) {
//마지막도시에서 시작 도시로 경로가 존재하지 않으면 return
if(w[index][0] == 0) return;
//그렇지 않으면 비용을 합에 더해준다.
else sum += w[index][0];
//최솟값이 초기값이거나 sum이 현재 최솟값보다 적은 경우
if(ans == -1 || ans > sum) {
ans = sum;
}
return;
}
//방문하지 않은 모든 도시로 가는 경우를 탐색
for(int i=1; i<n; i++) {
//i번째 도시를 방문했으면 넘어간다.
if(check[i]) continue;
//경로가 존재하지 않으면 넘어간다.
if(w[index][i] == 0) continue;
//i번째 도시를 방문
check[i] = true;
dfs(i,cnt+1,sum+w[index][i],check);
//i번째 도시를 가는 경우에서 돌아왔으므로 방문표시를 없애준다.
check[i] = false;
}
}
int main() {
cin >> n;
//비용을 w배열에 입력
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> w[i][j];
}
}
//최솟값을 저장
ans = -1;
//check 배열을 사용하여 방문 표시를 한다. false값으로 초기화
bool check[10]={false};
//0번째 도시를 시작점으로 잡고 탐색을 시작한다
check[0] = true;
dfs(0,0,0,check);
cout << ans;
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 14888. 연산자 끼워넣기 (0) | 2019.06.20 |
|---|---|
| [BOJ] 6603. 로또 (0) | 2019.06.20 |
| [BOJ] 10971. 외판원 순회2 (0) | 2019.06.20 |
| [BOJ] 10974. 모든 순열 (0) | 2019.06.20 |
| [BOJ] 9095. 1, 2, 3 더하기 (0) | 2019.06.20 |