🖊️ 문제

https://www.acmicpc.net/problem/1916

---

🖊️ 풀이

최소비용 -> 가중치의 합이 최소가 되도록..

어...........
노드 방문 순서를 좀 생각해보고..

일단 DFS로 풀었다
근데 보란듯이 메모리초과 ㅋ ㅋ

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <limits>
using namespace std;

vector<vector<pair<int, int>>> vec;
int cost[1001];
int start, dest;

void DFS(int cur, int curCost)
{
	if (cur == dest) return;
	for (auto& v : vec[cur]) {
		curCost += v.second;
		cost[v.first] = min(cost[v.first], curCost);
		DFS(v.first, curCost);
		curCost -= v.second;
	}
}

int main()
{
	int n, m;
	cin >> n;
	cin >> m;
	for (int i = 0; i <= n; i++) {
		vec.emplace_back(vector<pair<int, int>>());
		cost[i] = 987654321;
	}

	int s, e, c;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> c;
		vec[s].emplace_back(make_pair(e, c));
	}

	cin >> start >> dest;

	DFS(start, 0);

	cout << cost[dest] << endl;
}

아무래도 노드의 개수가 1,000개이기도 하고,, 재귀를 미친듯이 돌아서 스택오버플로우가 났을 것 같기도 하다.

근데

내가 몰랐던 것 뿐..

최소비용 구하는 문제는 다익스트라로 푸는게 좋다.

나는 여기서 구글링했고,, 그게 나았을것같음!!
다익스트라 알고리즘을 이용해서 문제를 풀어본 경험은 없어서,, 2학년때 알고리즘시간에 구현한게 다였다..

다시 공부한다는 마음으로 함!!

Dijkstra 알고리즘

우선순위 큐(이하 pq)를 이용해서 푼다.
노드의 인덱스와 비용을 pair에 담는다.

1. 시작 지점과 비용 0을 pq에 넣는다.
2. pq에서 탐색할 노드(이하 cur)을 꺼낸다.
3. cur의 비용이 해당 노드의 이미 설정된 현재 비용(이하 cost)보다 크면 더이상 탐색을 진행하지 않는다
4. 아니라면, cur과 인접한 노드들 (이하 next)에 대해서, cur를 거쳐 next로 가는 비용과 next에 이미 설정된 현재 비용(cost)을 비교한다. -> cur를 거쳐 next로 가는 비용이 더 작으면 cost를 갱신해주고, 해당 노드를 pq에 추가한다.
5. 2-4의 과정을 pq에 남은 노드가 없을 때까지 진행한다.

처음이라.. 몇 번 더 풀어봐야겠다.
알고리즘만 생각해보면 난이도는 크게 어렵지 않은 것 같아서 꼭,. 알고있어야할것같은 문제,,

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

struct compare {
	bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
		return a.second > b.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
vector<vector<pair<int, int>>> vec;
int cost[1001];
int start, dest;

void Dijkstra()
{
	pq.push(make_pair(start, 0));
	cost[start] = 0;

	while (!pq.empty()) {
		int cur = pq.top().first;
		int cst = pq.top().second;
		pq.pop();
		if (cst > cost[cur]) continue;

		for (auto& s : vec[cur]) {
			int next = s.first;
			int nextCost = cost[cur] + s.second;
			if (cost[next] > nextCost) {
				cost[next] = nextCost;
				pq.push(make_pair(next, nextCost));
			}
		}
	}
}

int main()
{
	int n, m;
	cin >> n;
	cin >> m;
	for (int i = 0; i <= n; i++) {
		vec.emplace_back(vector<pair<int, int>>());
		cost[i] = 987654321;
	}

	int s, e, c;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> c;
		vec[s].emplace_back(make_pair(e, c));
	}

	cin >> start >> dest;

	Dijkstra();

	cout << cost[dest] << endl;
}

다익스트라 알고리즘 관련은 따로 포스팅해야겠당.
씀