4번 문제
내가 풀이한 답
앞에서 풀었던 경로 탐색에서 조금 변형된 문제라고 생각했다. 기존에는 간선에 1 값을 넣었는데 1 값 대신에 가중치 값을 넣었고 temp 변수를 하나 선언하고 종점에 도달하기 전까지 더해서 종점에 도착하면 최솟값과 비교하는 것을 생각했다. 주의할 점은 아래 그림에서 두 번째 경로를 찾을 때 2-3, 3-4번으로 가는 가중치 값을 빼주는 것처럼 check값이 0으로 변할 때 temp에 가중치값도 빼줘야 한다.
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int map[21][21], check[21], n, minValue=77777, temp=0;
int dfs(int v){
if(v==n){
if(minValue > temp) minValue = temp;
}
else {
for(int i=1; i<=n; i++){
if(map[v][i]!=0 && check[i] == 0){
check[i] = 1;
temp += map[v][i];
dfs(i);
check[i] = 0;
temp -= map[v][i];
}
}
}
}
int main() {
//freopen("input.txt", "rt", stdin);
ios_base::sync_with_stdio(false);
int m, i, a, b, c;
cin >> n >> m;
for(i=0; i<m; i++){
cin >> a >> b >> c;
map[a][b] = c;
}
check[1] = 1;
dfs(1);
cout << minValue;
return 0;
}
결과는 통과하였다.
사이트의 답안
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[30][30], ch[30], n, cost=2147000000;
void DFS(int v, int sum){
int i;
if(v==n){
if(sum<cost) cost=sum;
}
else{
for(i=1; i<=n; i++){
if(map[v][i]>0 && ch[i]==0){
ch[i]=1;
DFS(i, sum+map[v][i]);
ch[i]=0;
}
}
}
}
int main(){
freopen("input.txt", "rt", stdin);
int m, i, a, b, c;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d %d %d", &a, &b, &c);
map[a][b]=c;
}
ch[1]=1;
DFS(1, 0);
printf("%d\n", cost);
return 0;
}
사이트의 답은 sum 값을 dfs 파라미터 인자로 넘겨주고 stack의 특성을 이용해서 sum 값이 stack에 저장되도록 하였다.
'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글
| 6. 전위순회, 중위순회, 후위순회 (0) | 2020.10.21 |
|---|---|
| 5. 최소비용(DFS : 가중치 방향그래프 인접리스트) (0) | 2020.09.23 |
| 3. 경로 탐색(DFS : 인접리스트 방법) (0) | 2020.09.23 |
| 2. 미로탐색(DFS) (0) | 2020.09.23 |
| 1. 경로 탐색(DFS) (0) | 2020.09.22 |
