5. 최소비용(DFS : 가중치 방향그래프 인접리스트)

    5번 문제   

 

 

---

    내가 풀이한 답   

 

 4번 문제와 똑같은 방법으로 풀었고 단순히 인접행렬을 인접리스트 방식으로 바꾸었다. 문제에서 입력 예제를 인접리스트로 나타내면 다음과 같다. 각각의 벡터들이 다른 인덱스값을 가지고 있고 인덱스 하나에 두 개의 값이 들어 있다. 하나는 간선으로 연결될 종점과 나머지 하나는 가중치 값이다. 

 

 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int> > map[21];
vector<int> check(21);
int n, minValue = 77777, temp = 0;

int dfs(int v){
	if(v==n) {
		if(minValue > temp) minValue = temp;
	}
	else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i].first] == 0){
				check[map[v][i].first] = 1;
				temp += map[v][i].second;
				dfs(map[v][i].first);
				check[map[v][i].first] = 0;
				temp -= map[v][i].second;
			}
		}
	}
}

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].push_back({b, c});
	}
	
	check[1] = 1;
	dfs(1);

	cout << minValue;
	return 0;
}

 

 

 결과는 통과하였다.

 

 

---

 

    사이트의 답안   

 

#include<stdio.h>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;	
int ch[30], cnt=0, n, cost=2147000000;
vector<pair<int, int> > map[30];

void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<cost) cost=sum;
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i].x]==0){
				ch[map[v][i].x]=1;
				DFS(map[v][i].x, sum+map[v][i].y);
				ch[map[v][i].x]=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].push_back(make_pair(b, c));
	}
	ch[1]=1;
	DFS(1, 0);
	printf("%d\n", cost);
	return 0;
}