[백준 / BOJ] C++ 1504 특정한 최단 경로

1504번: 특정한 최단 경로

 

문제

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

1504번: 특정한 최단 경로

 

 

풀이

정점 1에서 출발해 특정한 두 정점 v1, v2를 지나 정점 N에 도착하는 최단 거리를 출력하는 문제다. 다익스트라 알고리즘을 사용해 풀 수 있으며 양방향 그래프임을 기억하고 풀어야 하며 경로가 없는 경우 예외 처리 하는 게 힘들었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자.

[다익스트라 알고리즘 알아보기]

 

풀이는 1 -> v1 -> v2 -> N으로 가는 경우와 1 -> v2 -> v1 -> N으로 가는 경우 중 더 작은 값을 출력해 주면 된다. 양방향 그래프이기 때문에 중간에 어떤 과정을 거치든 상관없이 결국 v1, v2를 어떤 순서로 지나가느냐만 중요하다.

 

s와 e를 인자로 받아 정점 s에서 시작해 e까지 가는 최소 경로를 return 하는 다익스트라 함수를 만들었다. 만약 경로가 없는 경우는 위 과정에서 return 값이 한 번이라도 INF가 나오면 예외 처리를 해주었다.

 

 

코드

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

#define INF 2147483647

int N, E, v1, v2;
vector<pair<int, int>> graph[801]; // [정점][다음 정점, 거리]
vector<int> dist(801, INF), visited(801, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void init() {
  for (int i = 1; i <= N; i++) {
    visited[i] = 0;
    dist[i] = INF;
  }
}

int dijkstra(int s, int e) {
  init();               // 배열 초기화
  dist[s] = 0;          // 시작점 거리 0
  pq.push({0, s});      // 시작점만 pq에 추가
  while (!pq.empty()) { // pq가 비면 종료
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]); // curr이 방문한 정점이면 무시
    // 더 이상 방문할 수 있는 정점이 없으면 종료
    if (visited[curr])
      break;
    visited[curr] = 1; // 방문처리
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      // 거리가 갱신될 경우 pq에 추가
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> E;

  // 간선
  while (E--) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
  }

  cin >> v1 >> v2;

  // 다익스트라
  int ans;
  if (dijkstra(1, v1) == INF || dijkstra(v1, v2) == INF || dijkstra(v2, N) == INF || dijkstra(1, v2) == INF || dijkstra(v2, v1) == INF || dijkstra(v1, N) == INF) {
    ans = -1;
  } else {
    int t1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
    int t2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
    ans = min(t1, t2);
  }
  cout << ans << '\n';
  return 0;
}