백준 1916 최소 비용 구하기

처음 문제를 풀었을 때는 dfs를 이용해서 풀었는데, 시간 초과가 났다 ㅜ., 질문을 보니 다익스트라로 풀어야 된다는 것을 알게 됐다. 처음 접하는 개념이라, 익숙해지려면 비슷한 유형을 더 풀어봐야 할 것 같다.

다익스트라는  최단 경로 탐색 문제로, 출발 노드를 기준으로 가까운 노드들을 방문하여, 최단 경로를 계속 갱신하는 개념이다.

유의해야할 점은 이 문제에서는 같은 경로가 여러 번일 수 있고, 1 -> 3 경로를 입력한다고 3 -> 1 경로로 사용할 수 있는 것이 아니라는 것이다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int N, M;
int graph[1001][1001]; // 가중치 저장 2중 배열
void dijstra(int start);
int start, fin;
int INF = 1000000000; 
int find_small();
int dis[10001]; // 노드 별 최저 거리 저장할 배열
bool visit[10001]; // 해당 노드가 검사가 완료된 노드인지 확인할 배열

int main() {

	
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			graph[i][j] = INF; // 처음 가중치 모두 무한대로 초기화 
		}
	}
	int sum = 0;
	for (int i = 0; i < M; i++) {
		int num, next,length;
		cin >> num>>next>>length;
		if(graph[num][next]>length) // 저장된 값보다 적은 가중치면 갱신
		graph[num][next] = length;
	}


	cin >> start >> fin;
	dijstra(start); 

	cout <<  dis[fin] << endl;
}

int find_small() {  //가장 거리가 짧은 노드 찾기
	
	int min = INF;
	int index = 0;
	for (int i = 1; i <= N; i++) {
		if (dis[i] < min && !visit[i]) { 
			min = dis[i];
			index = i;
		}
	}

	return index;
}
void dijstra(int start) {
	for (int i = 1; i <= N; i++) {
		
		dis[i] = graph[start][i];
	}
	visit[start] = true; 
	dis[start] = 0;
	for (int i = 1; i < N - 1; i++) {
		int current = find_small(); // 가장 거리가 짧은 노드를 기준으로 삼음
		visit[current] = true;
		for (int j = 1; j <= N; j++) {
			if (!visit[j]) {
				if (dis[current] + graph[current][j] < dis[j]) { //기존보다 거리가 짧으면
					dis[j] = dis[current] + graph[current][j]; //갱신
				}
			}
		}
	}
}