4. 최소비용(DFS : 인접행렬)

    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에 저장되도록 하였다.