백준 1916 c++ "최소비용 구하기" -PlusUltraCode-

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

 

 

[필자 사고]

 

먼저, Input 함수는 그래프의 노드 수(N)와 간선 수(M)를 입력받고,

그래프를 저장할 2차원 벡터 arr, 각 노드까지의 최단 거리를 저장할 벡터 Distance,

그리고 각 노드의 방문 여부를 기록할 벡터 visited를 초기화한다.

그래프의 간선 정보를 입력받아 arr에 저장하며, 시작점과 끝점의 인덱스도 입력받는다.

 

그 다음, BFS 함수는 다익스트라 알고리즘을 사용하여 시작점에서 끝점까지의 최단 거리를 계산한다.

이 함수는 우선순위 큐를 사용해 시작점에서 출발하여 다른 노드로 가는 최단 경로를 탐색한다.

우선순위 큐에서 꺼낸 노드에 대해, 그 노드에서 연결된 다음 노드로 가는 경로를 계산하여,

더 짧은 경로가 발견되면 해당 경로를 갱신하고, 그 노드를 다시 큐에 추가하는 방식으로 동작한다.

BFS 함수에서 조심해야 될 점은 visted 관련 이다. 

다익스트라 알고리즘의 최대 핵심은 항상 최단거리일 경우만 node를 방문한다는 점이다.

그렇기에 

if (visited[nowNum])continue;
visited[nowNum] = true;

위와 같은 코드가 핵심이라고 생각한다. 이미 방문한 노드라면 무시하고 다시 시작
만약 방문하지 않았다면 최소 노드이기 때문에 방문처리하면 된다.

 

마지막으로, GameStart 함수는 BFS 함수에서 계산된 끝점까지의 최단 거리를 출력한다. 이는 시작점에서 지정된 끝점까지의 경로 중 가장 짧은 경로를 구하는 과정을 의미한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>


using namespace std;

typedef pair<int, int> Node;

const int MAX_NUM = 99999999;

int N, M;
vector<int> Distance;
vector<bool> visited;
vector<vector<Node>> arr;
int startIdx, endIdx;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	Distance.resize(N + 1, MAX_NUM);
	visited.resize(N + 1, false);
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		arr[s].push_back({ w,e });
	}
	cin >> startIdx >> endIdx;
}

void BFS() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,startIdx });
	Distance[startIdx] = 0;
	while (!pq.empty()) {
		int nowNum = pq.top().second;
		int nowWeight = pq.top().first;
		pq.pop();

		if (visited[nowNum])continue;
		visited[nowNum] = true;
		
		for (Node nextNode : arr[nowNum]) {
			int nextNum = nextNode.second;
			int nextWeight = nextNode.first;

			if (visited[nextNum])continue;

			if (Distance[nextNum] > Distance[nowNum] + nextWeight) {
				Distance[nextNum] = Distance[nowNum] + nextWeight;
				pq.push({ Distance[nextNum],nextNum });
			}
		}
	}
}

void GameStart() {
	BFS();
	cout << Distance[endIdx];
}

int main(void) {
	Input();
	GameStart();
}