[알골90제] 67번 최소비용 : DFS 가중치 방향 그래프 (인접행렬/인접리스트) STL : vector, pair

* 문제

 

가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요.

 

 

 

 

 

 

(!)목적지까지 가는 최소 비용은 보통 "다익스트라 알고리즘" 사용함

 

 

인접행렬 활용

// 67번 - 최소비용 DFS 인접행렬 (가중치 방향그래프)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int n, a, b, c, map[30][30], ch[30], cost = 999999999;
//cost는 minimum value

void DFS(int v, int sum) {

	if (v == n) {
		if (sum < cost)
			cost = sum;
	}
	else {
		for (int i = 1; i <= n; i++) {
			//가중치 값이 있냐?  == 0보다 크냐
			if (map[v][i] > 0 && ch[i] == 0) {
				ch[i] = 1;
				DFS(i, sum + map[v][i]);
				ch[i] = 0;
			}
		}
	}

}

int main() {

	int m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a][b] = c;
	}

	ch[1] = 1;
	DFS(1, 0); //두번째 파라미터는 비용값
	printf("%d", cost);

	return 0;
}

 

 

인접리스트 활용 (STL::vector, pair 사용)

 

*pair라는 자료구조?

 

2개의 데이터를 한쌍으로 묶어서 관리하는 것, 구조체하고 비슷한데 이건 2개만 한쌍으로 묶는 것

pair<int, int> p;

- p라는 이름으로 관리됨

노드를 생성해서 값을 넣는 것은

p=make_par(10,20);

printf("%d %d\n", p,first, p.second);

- 실제 노드가 생성됨

- 객체가 생성됨

- 값이 들어감

 

 

* pair 활용하여 인접리스트 만드는 핵심 코드

 

vector<pair<int, int> > map[30];

map[a].push_back(make_pair(b,c));

 

 

// 68번 - 최소비용 DFS 가중치 방향 그래프 (인접리스트)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, a, b, c, ch[30], cost = 999999999;
vector<pair<int, int> > map[30];

void DFS(int v, int sum) {

	if (v == n) {
		if (sum < cost)
			cost = sum;
	}
	else {
		for (int i = 0; i < map[v].size(); i++) {
			if (ch[map[v][i].first] == 0) { //방문안한 것 
										//map[v][i].first는 정점임
				ch[map[v][i].first] = 1;
				DFS(map[v][i].first, sum + map[v][i].second);
				ch[map[v][i].first] = 0;
			}
		}
	}
}

int main() {

	int m;
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b,c)); //c는?
	}

	ch[1] = 1;
	DFS(1, 0);
	printf("%d", cost);

	return 0;

}