68. 최소비용(DFS : 가중치 방향그래프 인접리스트) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

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

using namespace std;

int n, sum = 0, minNum = 2147000000;
vector<pair<int, int>> map[21];
int path[21];

void DFS(int x, int sum)
{
	if(x == n)
	{
		if(minNum > sum)
			minNum = sum;
	}
	else
	{
		for(int i = 0; i < map[x].size(); i++)
		{
			if(map[x][i].second > 0 && path[map[x][i].first] == 0)
			{
				path[map[x][i].first] = 1;
				DFS(map[x][i].first, sum + map[x][i].second);
				path[map[x][i].first] = 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);
		map[a].push_back(make_pair(b, c));
	}
	
	path[1] = 1;
	DFS(1, 0);
	
	printf("%d", minNum);
	
	return 0;
}

1. 67번 문제를 인접리스트를 활용하여 푼 문제이다.

 

2. vector<pair<int, int>> map[21]

- C#의 Dictionary의 느낌으로 생각하면 된다.

- int 형의 key, int 형의 value 를 저장하고 있는 vector 배열 map을 선언한 것이다.

- key에 접근할 때는 first, value에 접근할 때는 second로 접근한다.

- 원소를 추가할 때는 push_back(make_pair(key, value)) 또는 push_back({key, value}) 로 한다.

 

3. 이후 풀이는 66번 문제와 같다.