[C++] DFS 인접리스트 최소비용 (pair, vector)

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

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int n, minn = 2147000000;
vector<pair <int, int> > map[21];
int check[21];

void dfs(int v, int sum) {
	if (v == n) {
		minn = (sum < minn ? sum : minn);
	}
	else {
		for (int i = 0; i < map[v].size(); i++) {
			if (check[map[v][i].first] == 0) {

				check[map[v][i].first] = 1;
				dfs(map[v][i].first, sum + map[v][i].second);
				check[map[v][i].first] = 0;
			}
		}
	}
}

int main() {
	int m, i, start, end, val;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &start, &end, &val);
		map[start].push_back(make_pair(end, val));
	}
	check[1] = 1;
	dfs(1, 0);
	printf("%d", minn);
}

 

DFS를 2차원 배열의 그래프가 아닌 vector의 pair를 사용했다.

이런식으로 하는 것이 메모리적으로 봤을 때, 훨씬 좋다고 한다.

특히 dfs 함수에서 else-for-if문에서 i는 v와 연결되어있는 정점들의 인덱스 값을 나타낸다. 

map[v][i]는 pair 형태로 되어있기 때문에 first 값을 참조하면 v와 연결되어있는 노드 번호 second 값은 가중치가 된다.