[백준 / BOJ] C++ 18223 민준이와 마산 그리고 건우

18223번: 민준이와 마산 그리고 건우

 

문제

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

18223번: 민준이와 마산 그리고 건우

 

 

풀이

최단 경로 중에 민준이가 위치한 정점이 포함되는지 확인하는 문제다. 다익스트라 알고리즘으로 두 정점 간의 최단 경로를 구할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

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

 

건우가 위치한 P 정점이 최단 경로 위에 있다면, (시작점부터 P까지의 거리 + P부터 도착점까지의 거리 = 시작점부터 도착점까지의 거리)를 만족해야 한다. 따라서 다익스트라를 총 세 번 사용해서 풀 수 있다.

 

 

코드

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

#define INF 2147483647

int V, E, P;
vector<pair<int, int>> graph[5001]; // [정점][다음 정점, 거리]
vector<int> dist(5001, INF), visited(5001, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void init() {
  for (int i = 1; i <= V; 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 >> V >> E >> P;

  // 간선
  while (E--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }

  // 다익스트라
  if (dijkstra(1, P) + dijkstra(P, V) == dijkstra(1, V))
    cout << "SAVE HIM\n";
  else
    cout << "GOOD BYE\n";

  return 0;
}