DFS 최소 비용 (DFS 매개변수 이용)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>


using namespace std;
int n,cnt,minn=INT_MAX;
int map[21][21], ch[21];

void DFS(int v){
	if(v==n){
		if(cnt < minn){
			minn = cnt;
		}
		return;	
	}
	else{
		for(int i=1; i<=n; i++){
			if (map[v][i]>0 && ch[i]==0){
				ch[i]=1;
				cnt += map[v][i];
				DFS(i);
				ch[i]=0;
				cnt -=map[v][i];
			}
		}
	}
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int m, v, i,a,b,c;
	scanf("%d %d", &n, &m);
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a][b] = c;
	}
	
	DFS(1);
	printf("%d",minn);

}

 

DFS 함수의 매개변수에 결괏값을 넣어주면 

 

보다 간편하게 코드를 작성할 수 있다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>


using namespace std;
int n,cnt,cost=INT_MAX;
int map[21][21], ch[21];

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.txt","rt",stdin);
	int m, v, i,a,b,c;
	scanf("%d %d", &n, &m);
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a][b] = c;
	}
	
	DFS(1,0);
	printf("%d",cost);

}​