67. 최소비용(DFS : 인접행렬) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <stdio.h>
#include <vector>

using namespace std;

int n, minNum = 214700000;
int val[21][21];
int ch[21];

void DFS(int x, int sum)
{
	if(x == n)
	{
		if(sum < minNum)
			minNum = sum;
	}
	else
	{
		for(int i = 1; i <= n; i++)
		{
			if(val[x][i] > 0 && ch[i] == 0)
			{
				ch[i] = 1;
				DFS(i, sum + val[x][i]);
				ch[i] = 0;
			}
		}
	}
}

int main()
{
	int m, a, b, c;
	scanf("%d %d", &n, &m);
	
	for(int i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		val[a][b] = c;
	}
	
	ch[1] = 1;
	DFS(1, 0);
	
	printf("%d", minNum);
	
	return 0;
}

1. 가중치 값을 val[출발노드][도착노드] 에 저장하고, 가중치 누적값 sum을 매개변수로 넘겨준다.

2. 가중치 최솟값과 누적값을 비교하여 더 적은 값을 최솟값으로 한다.