[C++] 최소비용(DFS)

📄문제

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

 

⬇️ 입력

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

5 8 1 2 12 1 3 6 1 4 10 2 3 2 2 5 2 3 4 3 4 2 2 4 5 5

 

⬆️ 출력

총 가지수를 출력한다.

13

 

📝 풀이

#include <iostream>
#include <vector>
using namespace std;

static vector<vector<int>> graph;
static vector<bool> visited;
static int minCost = INT_MAX;
int N;

void DFS(int v = 0, int cost = 0)
{
	// v에 방문
	visited[v] = true;

	// 지금까지 누적된 비용이 min보다 높다면 리턴
	if (cost > minCost)
		return;

	// 목적지에 도착
	if (v == N - 1)
		minCost = minCost > cost ? cost : minCost;
	else
		for (int i = 0; i < N; ++i)
			if (!visited[i] && graph[v][i] >= 0)
			{
				// v에 방문하기
				DFS(i, cost + graph[v][i]);
				visited[i] = false;
			}
}

int main()
{
	int M;
	scanf_s("%d %d", &N, &M);

	graph = vector<vector<int>>(N, vector<int>(N, -1));
	visited = vector<bool>(N, false);

	int f, t, c; // from, to, cost
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &c);
		graph[f - 1][t - 1] = c;
	}

	DFS();

	printf("%d", minCost);
}

• DFS를 이용하여 다음 노드로 가는 비용을 더하여 최소비용을 갱신하여 정답을 냅니다.

 

#include <iostream>
#include <vector>
using namespace std;

static vector<pair<int, int>>* graph;
static vector<bool> visited;
static int minCost = INT_MAX;
int N;

void DFS(int v = 0, int cost = 0)
{
	// v에 방문
	visited[v] = true;

	// 지금까지 누적된 비용이 min보다 높다면 리턴
	if (cost > minCost)
		return;

	// 목적지에 도착
	if (v == N - 1)
		minCost = minCost > cost ? cost : minCost;
	else
		for (int i = 0; i < graph[v].size(); ++i)
			if (!visited[graph[v][i].first])
			{
				// v에 방문하기
				DFS(graph[v][i].first, cost + graph[v][i].second);
				visited[graph[v][i].first] = false;
			}
}

int main()
{
	int M;
	scanf_s("%d %d", &N, &M);

	graph = new vector<pair<int, int>>[N];
	visited = vector<bool>(N, false);

	int f, t, c; // from, to, cost
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &c);

		// 그래프에 목적지와 비용 삽입
		graph[f - 1].push_back({ t - 1, c });
	}

	DFS();

	printf("%d", minCost);
}

• 인접행렬을 사용하지 않고 인접 리스트를 이용하여 문제를 해결합니다.
• 문제 해결 방식 자체는 위와 동일하게 DFS로 접근합니다.