[백준/C++] 1753번 최단경로
목차
[문제]
백준_1753_최단경로
[접근법 / 분류]
다익스트라
- 필요한 변수
- 노드 정보(pair<int, int>)
- 그래프 정보(1차원 배열 : vetor<노드 정보>; index=노드번호)
- 최단 거리 정보(1차원 배열 : int; index = 노드 번호)
- 그래프 정보 입력
- 다익스트라 구현
- 우선순위 큐
- 시작 노드 정보 입력
- pq 빌 때까지 반복 : 갈 수 있고 & 최소 비용인 노드 탐색
- dis로 출력
[정답]
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define INF 1e9
using namespace std;
const int MAX = 20001;
vector<pair<int, int>> graph[MAX];
int dis[MAX]{};
int V{}, E{}, K{}; // 정점, 간선, 시작 노드 번호
void dijkstra(int start) {
priority_queue<pair<int, int>> pq; // 1. 비용, 2. 다음 노드 번호
// 비용이 먼저인 이유 : 비용을 기준으로 우선순위큐 안에서 정렬되게 하기 위해
pq.push({ 0, start});
dis[start] = 0;
while (!pq.empty()) {
// 비용에 마이너스를 붙이는 이유 : C++의 우선순위 큐=최대힙
/* ex) 비용
기본: 10, 9, 8, 7 : 비용값이 클수록 1번
음수: -7, -8, -9, -10 : 비용이 작을수록 1번(최소힙처럼 보이게 됨)
*/
int nowCost = -pq.top().first; // 현재까지의 비용
int nowNode = pq.top().second; // 현재 노드 번호
pq.pop();
// 이미 방문된 노드는 패스
if (dis[nowNode] < nowCost) continue;
// 현재 노드에서 갈 수 있는 노드들
for (int i = 0; i < graph[nowNode].size(); i++) {
int cost = nowCost + graph[nowNode][i].second;
// cost가 더 최단 거리라면 업데이트
int nextNode = graph[nowNode][i].first;
if (cost < dis[nextNode]) {
dis[nextNode] = cost;
pq.push(make_pair(-cost, nextNode));
}
}
}
}
int main() {
cin >> V >> E;
cin >> K;
for (int i = 0; i < E; i++) {
int u{}, v{}, w{}; // 시작 노드, 도착 노드, 비용
cin >> u >> v >> w;
graph[u].push_back({ v, w }); // (출발) u 노드 → (도착) v 노드 : (비용=w)
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(dis, dis + MAX, INF);
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (dis[i] == INF) cout << "INF\n";
else cout << dis[i] << "\n";
}
}
[풀이 중 겪은 문제 상황]
1. pq와 graph의 pair의 순서
<dijkstra의 pq>의 인수(pair<int cost, int node>)와 <main의 graph[u]>의 인수(pair<int v, int w>)를 헷갈림
둘다 pair<int, int>형식으로 push_back하고 출력하는데, pair의 값의 순서에서 게슈탈트 붕괴가 왔다.
pq의 입력
void dijkstra(int start) {
priority_queue<pair<int, int>> pq; // 1. 비용, 2. 다음 노드 번호
/* 중략 */
int nowCost = -pq.top().first; // 현재까지의 비용
int nowNode = pq.top().second; // 현재 노드 번호
/* 중략 */
int cost = nowCost + graph[nowNode][i].second;
/* 중략 */
int nextNode = graph[nowNode][i].first;
/* 중략 */
pq.push(make_pair(-cost, nextNode));
}
graph의 입력
vector<pair<int, int>> graph[MAX];
int main {
/* 중략 */
graph[u].push_back({ v, w }); // (출발) u 노드 → (도착) v 노드 : (비용=w)
/* 중략 */
}
즉,
pq는 {cost, node}
graph는 {node, cost}
순서로 입력되고 호출된다.
그런데 순간 pq == graph로 착각하면서, '둘이 같은 건데 왜 순서가 다르지?' 이러고 있었음..
2. pq의 pair의 first를 음수로 만드는 이유
void dijkstra(int start) {
/* 중략 */
int nowCost = -pq.top().first; // 현재까지의 비용
/* 중략 */
pq.push(make_pair(-cost, nextNode));
}이코테 최단 경로 강의에서는 C++의 우선순위 큐(priority Queue)는 최대힙이 기본이라 최소힙으로 만들기 위해서라고 했다.
이 말을 듣고 뭔가 머리 한 쪽에서는 계산 완료했는지 이해가 되면서도
반대쪽 머리(아마 좌뇌가 일 안한듯)에서는 이해가 안됐는지 '???' 이러고 있었음
[해결]
1. pq와 graph의 pair의 순서
코테 준비 스터디원들에게 코드 리뷰 때, pq와 graph의 의미를 설명하는 과정에서 게슈탈트 붕괴 디버프가 해제되었다.
스터디에서 코드 리뷰할 때는 각 변수들의 역할/의미를 설명하는 것과 코드 한 줄 한 줄 설명하는게 중요한 걸 이때 와닿음.
2. pq의 pair의 first를 음수로 만드는 이유
마찬가지로 스터디원들에게 설명하면서 이해 못하고 있던 반대쪽 머리가 깨달음을 얻음. 일해라 좌뇌
예를 들어 비용이 4, 1, 10, 7일 때
C++의 priority queue는 최대힙(내림차순)이므로 10, 7, 4, 1 순으로 정렬한다.
하지만 최단거리인 만큼 작은 게 제일 위로 올라와야한다.
목표 : 최소힙(오름차순)이므로 1, 4, 7, 10 순으로 정렬하는 것
그래서 4, 1, 10, 7에 마이너스를 붙여서 -4, -1, -10, -7로 만들면(pq.push(make_pair(-cost, nextNode))
최대힙에 따라 -1, -4, -7, -10으로 정렬된다.
그러면 목표했던 최단거리인 1이 가장 앞으로 오게 된다.
다만 pq에 들어간 값은 -1이므로, 호출(int newCost)할 때는 음수를 한 번 더 붙여서 -(-1)로 만들면 목표했던 1이 호출되게 된다.
[레퍼런스]
이코테 7강 우선순위 큐 (c++)
https://youtu.be/acqm9mM1P6o?si=Af2ibO2222f5DUZt&t=2272
[ps]
강의에서는 pq pair의 first를 음수로 받는 것으로 최소힙처럼 사용했다.
java도 priority queue의 comparator로 대소 비교가 가능하고,
오버라이딩을 통해 최대힙, 최소힙을 원하는 대로 변경 가능하다.
(참고1 java-priority queue, 참고2 java-interface-comparator)
c++에서는 이런 식으로 라이브러리 중에 오버라이딩할 수 있게 해둔거 없나 찾아보니
있었다!!
[Microsoft C++ 표준 라이브러리 파일] priority_queue::priority_queue
[cplusplus.com] Reference : construct priority_queue
알바가야해서 ps 관련 예제 작동은 다음시간에 계속 작성 예정