[백준 / BOJ] C++ 2307 도로검문

2307번: 도로검문

 

문제

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

2307번: 도로검문

 

 

풀이

어느 한 간선을 차단하여 1에서 N까지 최단 경로가 얼마나 거리를 늘릴 수 있는지 구하는 문제다. 다익스트라 알고리즘으로 해결할 수 있다.

다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

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

 

이 문제에서 중요한 것은 최단 경로 이외엔 차단할 필요가 없다. 왜냐하면 어차피 최단 경로로 지나가면 그만이기 때문이다.

 

그럼 먼저 최단 거리와 최단 경로를 구해준다. 최단 경로를 구하는 방법은 아래 문제를 참고하자.

[11779 최소비용 구하기 2 문제] | [11779 최소비용 구하기 2 해설]

 

최단 경로의 한 간선의 가중치를 INF로 바꾼다. 그리고 다익스트라 알고리즘을 사용해 최단거리를 구한다. 만약 다익스트라 return 값이 INF라면 경로가 이어지지 않는 경우가 있으므로 -1을 출력한다.

 

그렇지 않다면 원래 최단 거리와의 차를 구해 최댓값을 갱신해 주고 간선을 다시 연결해 준다.

 

위 과정을 반복해 차의 최댓값을 출력하면 정답이다.

 

* 주의 *

INF를 int형 최댓값인 2147483647로 했더니 integer overflow가 나서 오류가 났다. 적당히 1e9 정도로 해도 괜찮은 것 같다.

 

 

코드

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

#define INF 1000000000

int N, M;
vector<pair<int, int>> graph[1001]; // [정점][다음 정점, 거리]
vector<int> dist(1001, INF), visited(1001, 0), bef(1001, -1);
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;
        bef[next] = curr;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

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

  cin >> N >> M;

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

  // 다익스트라, 최단거리
  int m = dijkstra(1, N), ans = -1;

  // 최단 경로
  int tmp = N;
  vector<int> way;
  while (tmp > 0) {
    way.push_back(tmp);
    tmp = bef[tmp];
  }

  // 최단 경로의 각 간선마다 차단하며 탐색
  for (int i = 0; i < way.size() - 1; i++) {
    int a = way[i], b = way[i + 1];
    int a_idx, b_idx, a_cost, b_cost;
    // 제거할 a -> b 간선 탐색
    for (int j = 0; j < graph[a].size(); j++)
      if (graph[a][j].first == b) {
        a_idx = j;
        a_cost = graph[a][j].second;
        graph[a][j].second = INF;
        break;
      }
    // 제거할 b -> a 간선 탐색
    for (int j = 0; j < graph[b].size(); j++)
      if (graph[b][j].first == a) {
        b_idx = j;
        b_cost = graph[b][j].second;
        graph[b][j].second = INF;
        break;
      }
    // 다익스트라
    int time = dijkstra(1, N);
    // 연결이 안되면
    if (time == INF) {
      ans = -1;
      break;
    }
    // 지연 시간 계산, 최댓값 갱신
    int gap = time - m;
    ans = max(ans, gap);
    // 간선 재연결
    graph[a][a_idx].second = a_cost;
    graph[b][b_idx].second = b_cost;
  }
  // 정답 출력
  cout << ans << '\n';
  return 0;
}