[c++] 최소비용(DFS: 인접행렬)

DFS를 이용해 가중치 방향 그래프가 주어진 것을 보고 N번 정점으로 가는 최소 비용을 출력하는 프로그램을 작성하는 문제이다.

 

내가 작성한 코드(오답)

#include <iostream>
#include <vector>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int map[30][30], n, m, ch[30], sum, min_val=214700000;
void DFS(int v){
	int i;
	if(v==n){
			printf("sum: %d\n", sum);
		if(sum<min_val){
			printf("min sum: %d\n", sum);
			min_val=sum;
		}
		sum=0;
	} else {
		for(i=1; i<=n; i++){
			if(map[v][i]!=0 && ch[i]==0){
				ch[i]=1;
				printf("i: %d, ", i);
				printf("ch[1]: %d, ", ch[i]);
				printf("map vi: %d\n", map[v][i]);
				sum+=map[v][i];
				DFS(i);
				ch[i]=0;
				printf("i: %d, ", i);
				printf("ch[0]: %d\n", ch[i]);
			}
		}
	}
}

int main() {
	int a, b, c, i, j;
	freopen("input.txt", "rt", stdin);
	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);
	
	printf("%d", min_val);
	return 0;
}

 

 

내가 작성한 코드는 DFS함수에 DFS(i)를 넘겨주고 v==n조건이 충족했을 떄 sum이 min_val인지만 확인한다.

그다음 sum을 0으로 초기화했다.

이렇게 하게되면 v==n조건을 충족시키고 나서 이전 재귀함수로 돌아가면서 ch[i]를 풀어주게 되는데

이 때 sum이 0으로 초기화 되어 있기 때문에 이전까지의 합을 알수가 없다.

 

이전의 합을 DFS에 i와 함께 넘겨주어야 이전까지의 합에 또 더할 수가 있는 것이다.

아래는 위 코드에서 printf로 출력한 값들이다.

틀린 코드의 결과값이다.

설명하면 v==n조건을 만족해서 sum을 구한 후 이전 sum값을 0으로 초기화하여 알 수 없으므로

되돌아가면서 map[v][i]!=0 && ch[i]==0에 만족하는 조건을 만나면 sum=0인 상태에서 map[v][i]값을 더하게 된다.

따라서 min_sum값이 터무니없이 작아지게 된다.

따라서 아래 코드처럼 작성해야 한다.

 

 

 

정답코드

#include <iostream>
#include <vector>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int map[30][30], n, m, ch[30], sum, min_val=214700000;
void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<min_val){
			min_val=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() {
	int a, b, c, i, j;
	//freopen("input.txt", "rt", stdin);
	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", min_val);
	return 0;
}

위 코드와 다르게 DFS(i, sum+map[v][i])로 값을 넘겨주고 있다. 

이렇게 해주면 이전 sum을 함께 넘겨주게 되므로 v==n까지 전진하고 다시 되돌아 가는 과정에서

되돌아온 지점까지의 sum을 알 수가 있다.

v==n조건을 만족해서 sum을 구한 후 이전 sum값을 0으로 초기화하지 않고

되돌아가면서 map[v][i]!=0 && ch[i]==0에 만족하는 조건을 만나면

sum+map[v][i]으로 누적된 sum을 구할 수 있어 정상적인 sum값만 구해진다.