[백준 / BOJ] C++ 9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

문제

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

 

풀이

다익스트라 알고리즘을 사용해 0에서부터 M-1까지 도달하는 최단 거리를 구하고 경로를 출력한다. 최단 거리를 구할 수 없으면 -1을 출력한다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

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

 

bef 배열을 만들어 최단 경로를 구해줬다. dist 배열을 갱신할 때마다 a -> b로 이동했다면 bef[b] = a 형태로 저장하고 다익스트라 알고리즘이 끝난 후 bef[M-1]부터 역으로 돌아가며 경로를 찾아낸다.

 

비슷한 문제로 [11779 최소비용 구하기 2 문제] | [11779 최소비용 구하기 2 해설]가 있다.

 

 

코드

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

#define INF 1000000000

int T, N, M;
vector<pair<int, int>> graph[20];                       // [정점][다음 정점, 거리]
vector<int> dist(20, INF), visited(20, 0), bef(20, -1); // 정점까지의 거리, 방문 여부, 경로
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void init() {
  for (int i = 0; i < M; i++) {
    graph[i].clear();
    visited[i] = 0;
    bef[i] = -1;
    dist[i] = INF;
  }
}

int dijkstra(int s, int e) {
  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;
        bef[next] = curr;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

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

  cin >> T;

  for (int i = 1; i <= T; i++) {
    cin >> N >> M;

    init(); // 배열 초기화

    // 간선
    while (N--) {
      int x, y, z;
      cin >> x >> y >> z;
      graph[x].push_back({y, z});
      graph[y].push_back({x, z});
    }

    cout << "Case #" << i << ": ";

    // 경로가 없는 경우
    if (dijkstra(0, M - 1) == INF) {
      cout << -1;
    } else { // 경로가 있는 경우
      vector<int> way;
      int tmp = M - 1;
      while (tmp >= 0) {
        way.push_back(tmp);
        tmp = bef[tmp];
      }
      for (int i = way.size() - 1; i >= 0; i--)
        cout << way[i] << ' ';
    }
    cout << '\n';
  }
  return 0;
}