[백준] 1504번: 특정한 최단 경로 (C++)

문제 링크

1504번: 특정한 최단 경로

---

오랜만에 다익스트라 문제를 풀어봤습니다!

알고리즘이 어떻게 돌아가는지는 알긴했는데 오랜만이라 까먹어서(...) 다익스트라 알고리즘만 구글링으로 참고했습니다.

이번 문제는 (다익스트라만 알면) 그렇게 어렵지는 않았고, 아이디어만 잘 생각하면 풀 수 있는 문제여서 기분 좋게 코딩할 수 있었습니다.

풀이

1부터 N까지 갈 때, 두 점(v1, v2)을 반드시 지나는 최단경로의 길이를 코딩하면 됩니다.

필자의 처음 생각으로는, 1부터 N까지 가는데 vst 배열같은 걸로 체크를 하면 되지 않을까 했는데, 생각해보니 최단경로이기 때문에 지나지 않는 경우가 있을 수밖에 없었습니다. 고민한 후에, 다음 풀이를 생각해 냈습니다.

1. 어차피 두 점을 반드시 지나기 때문에, 명시적으로 거리를 구해주면 됩니다.
2. 즉, (1 ➡ v1) 경로, (v1 ➡ v2) 경로,  (v2 ➡ N) 경로를 각각 최단경로 길이를 구해서 더해주면 됩니다.
3. 단, (v1 ➡ v2) 경로와 (v2 ➡ v1) 경로의 길이가 서로 다를 수도 있기 때문에, (1 ➡ v2) 경로, (v2 ➡ v1) 경로,  (v1 ➡ N) 경로로 가는 최단경로 길이를 한 번 더 구해서 위 2번과 비교하여 최솟값을 출력해줍니다.

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int n, e;
vector<pair<int, int>> graph[801];
int dis[801];
int v1, v2;

int dk(int a, int b) {
  fill(dis, dis + n + 1, (int)1e9);
  
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  dis[a] = 0;
  pq.push({0, a});
  while (!pq.empty()) {
    auto [d, x] = pq.top(); pq.pop();

    for (auto [nd, nx]: graph[x]) {
      nd += d;
      if (nd < dis[nx]) {
        dis[nx] = nd;
        pq.push({nd, nx});
      }
    }
  }
  return dis[b];
}

int go(int path[4]) {
  int sum = 0;
  for (int i = 0; i < 3; i++) {
    int a = path[i];
    int b = path[i + 1];
    if (a == b) continue;
    int len = dk(a, b);
    if (len >= (int)1e9) {
      sum = -1;
      break;
    } else sum += len;
  }
  return sum;
}

void solve() {
  cin >> n >> e;
  while (e--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({c, b});
    graph[b].push_back({c, a});
  }
  cin >> v1 >> v2;
  
  int path[] = {1, v1, v2, n};
  int path2[] = {1, v2, v1, n};
  cout << (min(go(path), go(path2)));
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  solve();
  return 0;
}

 

위 코드를 실행하면, 총 6번의 다익스트라 알고리즘을 돌리게 됩니다.

배운점

• 다익스트라 알고리즘을 복습해 볼 수 있었습니다.
• 우선순위 큐의 기본모양(priority_queue<int>)이 최대힙임을 다시 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!