[백준 / BOJ] C++ 17396 백도어

17396번: 백도어

 

문제

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

17396번: 백도어

 

 

풀이

0번에서 N-1번까지 가는 최단 경로를 구하는 문제다. 몇 가지 예외만 처리해 주면 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

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

 

예외인 경우는 넥서스를 제외한 시야가 밝혀져 있는 정점은 지나갈 수 없다. 따라서 간선을 입력받을 때 해당 정점과 연결된 모든 간선을 조건을 추가해 연결하지 않았다. 그리고 양방향임에 주의하며 경로가 없는 경우엔 -1을 출력한다. 또 범위가 크기 때문에 INF가 100,000 × 100,000 + 1 이상이어야 한다.

 

 

코드

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

#define INF 10000000001

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

  // 시야가 있는 곳
  vector<int> v(N);
  for (int i = 0; i < N; i++)
    cin >> v[i];

  // 간선
  vector<pair<int, int>> graph[100001]; // [정점][다음 정점, 거리]
  while (M--) {
    int a, b, t;
    cin >> a >> b >> t;
    // 넥서스 위치가 아니면서 시야가 밝혀져있는 곳과 연결된 간선은 제외
    if (a != N - 1 && b != N - 1 && (v[a] == 1 || v[b] == 1))
      continue;
    graph[a].push_back({b, t});
    graph[b].push_back({a, t});
  }

  // 다익스트라
  vector<int> visited(100001, 0);
  vector<long long> dist(100001, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  dist[0] = 0;          // 시작점 거리 0
  pq.push({0, 0});      // 시작점만 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});
      }
    }
  }

  // 경로가 없으면 -1
  if (dist[N - 1] == INF)
    cout << "-1\n";
  else
    cout << dist[N - 1] << '\n';
  return 0;
}