🙇‍♀️최소비용(DFS : 인접행렬)

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

image

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 

그 다음부터 M줄에 걸쳐 연결정보가 주어진다. 

▣ 출력설명
총 가지수를 출력한다.

▣ 입력예제 1 
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

▣ 출력예제 1
13

🚀풀이

이전 경로 탐색처럼 풀되 방문할 때 cost계산을 같이 해주면 된다.

void DFS(int here)
{
	if (here > n)
		return;
	if (here == n)
	{
		res = min(res, totalCost);
	}
	for (int there = 1; there <= n; ++there)
	{
		if (board[here][there] == 0)
			continue;
		if (visited[there])
			continue;

		visited[here] = true;
		totalCost += board[here][there]; // 비용 계산
		DFS(there);
		visited[here] = false;
		totalCost -= board[here][there]; // 비용 철회
	}
}

위의 그래프에서 DFS코드를 돌렸을 때 위치와 cost계산을 다음과 같이 나온다.

1방문
totalCost : 12

2방문
totalCost : 14

3방문
totalCost : 17

4방문
totalCost : 22

5방문
totalCost : 22
res : 22

4방문 취소
totalCost : 17

3방문 취소
totalCost : 14

2방문 취소
totalCost : 12

2방문
totalCost : 14

5방문
totalCost : 14
res : 14

2방문 취소
totalCost : 12

1방문 취소
totalCost : 0

1방문
totalCost : 6

3방문
totalCost : 9

4방문
totalCost : 11

2방문
totalCost : 13

5방문
totalCost : 13
res : 13

2방문 취소
totalCost : 11

4방문 취소
totalCost : 9

4방문
totalCost : 14

5방문
totalCost : 14
res : 13

4방문 취소
totalCost : 9

3방문 취소
totalCost : 6

1방문 취소
totalCost : 0

1방문
totalCost : 10

4방문
totalCost : 12

2방문
totalCost : 14

2방문 취소
totalCost : 12

2방문
totalCost : 14

5방문
totalCost : 14
res : 13

2방문 취소
totalCost : 12

4방문 취소
totalCost : 10

4방문
totalCost : 15

5방문
totalCost : 15
res : 13

4방문 취소
totalCost : 10

1방문 취소
totalCost : 0

13

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, totalCost = 0, res = 123456789;
vector<vector<int>> board;
vector<bool> visited;

void setting()
{
	cin >> n >> m;
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	visited = vector<bool>(n + 1);

	for (int i = 1; i <= m; ++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;
		board[a][b] = cost;
	}
}

void DFS(int here)
{
	if (here > n)
		return;
	if (here == n)
	{
		res = min(res, totalCost);
		cout << here << "방문" << endl;
		cout << "totalCost : " << totalCost << endl;
		cout << "res : " << res << endl;

		cout << endl;
	}
	for (int there = 1; there <= n; ++there)
	{
		if (board[here][there] == 0)
			continue;
		if (visited[there])
			continue;

		visited[here] = true;
		totalCost += board[here][there];
		cout << here << "방문" << endl;
		cout << "totalCost : " << totalCost << endl;
		cout << endl;
		DFS(there);
		visited[here] = false;
		totalCost -= board[here][there];
		cout << here << "방문 취소" << endl;
		cout << "totalCost : " << totalCost << endl;
		cout << endl;
	}
}

void solve()
{
	setting();

	DFS(1);

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고