[백준][다익스트라] 1916 최소비용 구하기 c++ 구현

목차

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

1916번: 최소비용 구하기

문제

 

 

 

구현 방향

다익스트라 알고리즘을 이용해 구현했다. 다른 bfs나 dfs를 사용하게 되면 시간초과가 뜰 것이다..

 

 

 

 

구현 시 주의할 점

처음 가중치를 설정할 때 최대 가중치를 10만을 약간 넘게 잡으면 틀린다.

그이유는 목표 노드까지 가는 비용의 최대치가 10만이 아니기 때문이다.

따라서 훨씬 10만 보다 큰 수로 해주어야 한다.

 

노드에 비해 간선의 수가 훨씬 많으므로 더 작은 간선을 석택해 주는 방식으로 해야 한다.

 

 

 

 

다익스트라 알고리즘 절차

1. 출발 노드를 설정합니다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드르 선택합니다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.

5. 위 3~4 과정을 반복합니다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int INF = 100000002;  //주의: 출발 노드에서 목표 노드까지 가는 비용의 최대치가 10만이 아님.

vector<int> d;
vector<bool> visit;
int N, M, start, target;
vector<int> m[1001];

int small_index() {
	int i, min = INF, min_idx=0;
	for (i = 0; i <= N; i++) {
		if (!visit[i]) {
			if (min > d[i]) {
				min_idx = i;
				min = d[i];
			}
				
		}
	}
	return min_idx;
}

void Dijkstra(int start) {
	int i, j;
	for (i = 0; i <= N; i++) {
		 d[i] = m[start][i];
	}
	visit[start] = true;
	for (i = 0; i <= N-2; i++) {
		int cur = small_index();
		visit[cur] = true;
		for (j = 0; j <= N; j++) {

			if (!visit[j]) {   //방문했는지 여부 확인
				if (d[cur] + m[cur][j] < d[j])
					d[j] = d[cur] + m[cur][j];
			}
		}
	}
}

int main() {
	int u, v, w, i, j;
	cin >> N;
	cin >> M;
	
	for (i = 0; i <= N; i++) {
		for (j = 0; j <= N; j++) {
			m[i].push_back(INF);   // 가중치 INF로 
			if (i == j) {   //자기 자신이면 0으로 초기화
				m[i][j] = 0;
				m[j][i] = 0;
			}
				
		}
	}

	for ( i = 0; i < M; i++) {
		cin >> u >> v >> w;
		if (m[u][v] != INF)
			m[u][v] = min(m[u][v], w);   //단방향 그래프 ->더 작은 가중치를 설정해줌
		else 
			m[u][v] = w;  
		
		    
	}

	cin >> start >> target;

	for (i = 0; i <= N; i++) {  //초기 노드개수만큼 초기화
		visit.push_back(false);
		d.push_back(INF);
	}

	Dijkstra(start);
	cout << d[target];

}

 

 

 

참고

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘