[백준] 1916번 최소비용 구하기

문제: 1916번: 최소비용 구하기

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

// 각 노드들의 인접리스트를 만들 이차원 벡터
// a 번째 노드와 연결되어 있는 b 번째 노드까지의 거리를 저장해둔 값
// adj_list[x].push(make_pair(y,z)) 에서 x 는 a 번째 노드, y 는 b 번째 노드, z 는 거리
vector<pair<int, int>> adj_list[100001]; // 인접 리스트

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; // 도시의 개수
	cin >> n;
	int m; // 버스의 개수
	cin >> m;

	// 0번 인덱스는 안 쓸 것..
	// a 번째 노드와 연결되어 있는 b 번째 노드까지의 거리 저장하기
	for (int i = 0; i < m; i++) {
		int from, dest, distance;
		cin >> from >> dest >> distance;
		from--, dest--;

		// first: distance, second: dest
		pair<int, int> edge = make_pair(distance, dest);
		adj_list[from].push_back(edge);
	}

	// 출발 도시, 도착 도시
	int from, dest;
	cin >> from >> dest;
	from--, dest--;


	vector<int> prev = vector<int>(n); // 이전 정점 저장
	for (int i = 0; i < n; i++)
		prev[i] = -1; // -1 로 초기화..

	vector<int> distance = vector<int>(n, INT_MAX); // 시작 정점과의 거리

	distance[from] = 0; // 당연히 자신 사이의 거리는 0..
	set<int> selectedNodes; // 이미 선택된 노드 번호 저장..


	// 최소힙으로 동작하도록..
	// 후보가 되는 것들 넣어놓기(가중치와 도착 노드 번호)
	// 음.. 가중치를 기준으로 최소힙으로 동작하도록 해야할 것 같다..
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minNodes;
	minNodes.push(make_pair(0, from)); // 일단 맨 처음은 시작 노드 넣어놓고 시작..


	// 후보가 될 수 있는 것들이 없으면 그냥 나가도록..
	while (!minNodes.empty()) {
		pair<int, int> node = minNodes.top();
		minNodes.pop();
		
		int w = node.first; // 가중치
		int u = node.second; // 도착 정점 번호

		// 만약 도착 정점이 이미 집합에 속해있으면 포기..
		// selectedNodes.find(u) 의 값이 selectedNodes.end() 의 값과 같으면 집합에 존재하지 않는 것..
		if (selectedNodes.find(u) != selectedNodes.end()) continue;

		// 집합에 속해있지 않으면 넣을 것..
		selectedNodes.insert(u);

		// 이제 집합에 새로 u 가 속하게 되었으니까 u 와 이웃하는 노드들을 minNodes 에 넣기(물론 해당 노드가 집합에 속해있지 않을 때!)
		for (int i = 0; i < adj_list[u].size(); i++) {
			int w_uv = adj_list[u][i].first; // u 와 연결된 노드 사이의 가중치
			int v = adj_list[u][i].second; // u 와 연결된 노드

			// 집합에 존재하지 않고, 새로운 거리가 기존 거리보다 적으면 minNodes 에 넣어주기..
			if ((selectedNodes.find(v) == selectedNodes.end()) && (distance[u] + w_uv < distance[v])) {
				distance[v] = distance[u] + w_uv;
				prev[v] = u;
				minNodes.push(make_pair(distance[v], v));
			}
		}
	}
	cout << distance[dest] << "\n";


	return 0;
}

 

음.. 다익스트라를 이용해서 문제를 풀어보는 건 처음이라 다른 코드를 많이 참고했다. MST 는 Kruskal 알고리즘이랑 Disjoints Set 이용하면 돼서 쉽게 풀었는데 다익스트라는 Prim 알고리즘이랑 비슷하게 해야 해서 너무 어려웠다.

사실 MST 문제 풀 때 Prim 알고리즘으로는 전혀 안 풀고 Kruskal 로만 풀었는데 그것 때문에 연습이 전혀 안 되어 있어서 더 어려웠던 것 같다;;

 

MST 복습할 때 Kruskal 말고도 Prim 방식으로도 풀어봐야겠다.. ㅠ_ㅠ

 

다익스트라는 Prim 알고리즘처럼, 정점 집합 S를 점진적으로 확장해가는 방식이라고 한다.

 

• Step1: 시작 정점 s만 포함하는 집합 S={s} 생성
• Step2: S 에 포함되지 않은 정점 중 s 와 가장 가까운 정점 v 를 찾아 S 에 편입
  • v 의 이전 노드를 저장해서 경로 찾을 때 활용한다.

모든 정점이 S 에 포함될 때까지 Step2 를 반복한다.

 

다익스트라 알고리즘이 필요로 하는 것은 이전 정점을 저장할 배열, 시작 지점과의 거리를 저장할 배열, 후보자 노드들을 저장할 우선 순위 큐가 있다. 추가로 링크드 리스트를 표현할 배열도 필요하다. 내 코드 상에서는 링크드 리스트의 요소 자료형이 pair<int, int> 이와 같은데 first 는 가중치, second 는 도착점이다.

 

while 문을 돌면서 집합에 어떤 노드가 새로 추가되면 그 노드와 이웃하는 노드들의 정보를 업데이트 해줘야 한다. 이웃하는 노드가 집합에 속해있지 않고 d[u] + w_uv 의 값이 d[v] 의 값 보다 작아야 비로소 이웃하는 노드를 minNodes 에 넣을 수 있다. 그리고 이웃하는 노드의 이전정점은 u 이므로 prev[v] = u 이렇게 해줘야 한다.

 

으.. 너무 어려워서 MST 문제 풀이랑 다르게 설명도 잘 못하겠다. 내일 스스로 풀어보고 다시 정리해야 할 것 같다. 그래도 얘도 계속 풀다보면 괜찮아질 거라 믿는다.. Disjoints Set, MST, Greedy 다 어려웠는데 지금은 스스로 풀 수 있으니까 얘도 그럴 수 있겠지!!! 파이팅!!!!!!!!

 

 

 

참고자료:

1) 문제

[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!)

[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!)

 

2) set 사용법

C++ set 사용법과 설명...

C++ set 사용법과 설명...

 

3) 배열

vector 만 주구장창 쓰니까 배열 쓰는 법을 순간 까먹어서 너무 충격받았다... 기본이 안 되어있다니...

일단 여기서 잠깐 정리 해놓겠다.

 

• 방법 1: 고정 크기 배열

vector<pair<int, int>> adj_list[100]; // 크기가 100인 배열, 각 요소는 vector<pair<int, int>>

 

• 방법 2: 동적 크기 배열 (동적 할당)

int n = 100; // 필요한 크기
vector<pair<int, int>>* adj_list = new vector<pair<int, int>>[n];

// 동적 배열은 사용 후 반드시 delete 해줘야 한다..
delete[] adj_list;

 

• 방법 3: std::vector로 배열 대체 (가변 크기)

int n = 100; // 필요한 크기
vector<vector<pair<int, int>>> adj_list(n); // 크기가 n인 2차원 벡터