[백준 / BOJ] C++ 5719 거의 최단 경로

5719번: 거의 최단 경로

 

문제

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

5719번: 거의 최단 경로

 

 

풀이

정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다.

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

 

먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 최단 경로인 경로를 모두 지워야 한다. 최단 경로가 여러 개 일 수 있으니 BFS를 사용해 모든 경로가 제거되도록 한다. 주의할 점은 최단 경로를 끊는 것이 아니라 최단 경로에 포함된 모든 간선을 끊어야 한다. 모든 최단 경로를 제거하고 난 후 한 번 더 다익스트라 알고리즘을 사용해 답을 구할 수 있다. 경로를 제거하는 방법은 간선의 cost를 INF로 할당해 줬다. (절대 지나가지 않도록)

 

틀린 풀이

다익스트라 알고리즘을 사용해 처음 최단 경로를 구하고 해당 경로를 제거해 준다. 그리고 다시 다익스트라 후 앞선 최단 경로와 길이가 같으면 제거를 반복하며 새로운 길이가 나오면 멈추도록 했다. 아쉽게도 TLE 시간초과가 났다.

 

BFS로 시작 정점부터 시작해 현재까지의 거리 + 다음 정점까지 거리가 최단거리이면서 다음 정점이 도착지점이면 해당 경로를 모두 제거하도록 구상을 했다. 그러나 경로를 끊는 것은 가능하나 모든 간선을 제거하는 것은 구현이 힘들어서 포기했다.

 

맞은 풀이

그 다음은 BFS를 사용하나 역 추적을 하는 것이다. 다익스트라 알고리즘이 끝나면 dist배열은 시작점으로부터 각 정점까지의 거리를 가지고 있다. 따라서 만약 최단 경로가 0 -> 1 -> 5 -> 6인 경우 dist[6] - dist[5] 는 5 -> 6인 간선의 가중치와 같다. 이때 이 간선을 제거하고 다음 정점인 5에 대해서 또 탐색을 통해 반복해서 제거한다.

 

이미 간선을 제거한 경우, 해당 간선을 다시 끊는 등 재방문을 하면 안된다. 그러면 큐에 무한정 추가되어 메모리 초과가 난다. 따라서 조건에 아직 안끊긴 경우만 끊고 큐에 추가하도록 하거나 방문 처리를 통해 해결해 주면 된다. 두 방법 모두 아래 코드를 공유하겠다.

 

 

코드

조건을 추가한 경우

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int N, M, S, D;
vector<pair<int, int>> graph[500], reverse_graph[500];
vector<int> dist(500, INF), visited(500, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

// 다익스트라
int dijkstra(int s, int e) {
  // 배열 초기화
  for (int i = 0; i < N; i++) {
    visited[i] = 0;
    dist[i] = INF;
  }
  dist[s] = 0;
  pq.push({0, s});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

void bfs() {
  queue<int> q;
  // 도착지점부터 역추적
  q.push(D);
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    for (int i = 0; i < reverse_graph[curr].size(); i++) {
      int next = reverse_graph[curr][i].first;
      int cost = reverse_graph[curr][i].second;
      // 최단경로라면
      if (dist[curr] - dist[next] == cost)
        for (int j = 0; j < graph[next].size(); j++)
          // 해당 간선이면서 아직 끊기지 않은 경우
          if (graph[next][j].first == curr && graph[next][j].second != INF) {
            // 간선 제거
            graph[next][j].second = INF;
            q.push(next);
            break;
          }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  while (1) {
    // 그래프 초기화
    for (int i = 0; i < N; i++) {
      graph[i].clear();
      reverse_graph[i].clear();
    }
    cin >> N >> M;
    if (!(N + M))
      break;
    cin >> S >> D;
    // 간선 입력
    while (M--) {
      int u, v, w;
      cin >> u >> v >> w;
      graph[u].push_back({v, w});
      // 역 추적 그래프
      reverse_graph[v].push_back({u, w});
    }
    // 최단 경로
    dijkstra(S, D);
    // 최단 경로 제거
    bfs();
    // 거의 최단 경로
    int ans = dijkstra(S, D);
    cout << (ans == INF ? -1 : ans) << '\n';
  }
  return 0;
}

 

방문 처리를 한 경우

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int N, M, S, D;
vector<pair<int, int>> graph[500], reverse_graph[500];
vector<int> dist(500, INF), visited(500, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

// 다익스트라
int dijkstra(int s, int e) {
  // 배열 초기화
  for (int i = 0; i < N; i++) {
    visited[i] = 0;
    dist[i] = INF;
  }
  dist[s] = 0;
  pq.push({0, s});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

void bfs() {
  queue<int> q;
  vector<bool> vst(500, 0);
  // 도착지점부터 역추적
  q.push(D);
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    for (int i = 0; i < reverse_graph[curr].size(); i++) {
      int next = reverse_graph[curr][i].first;
      int cost = reverse_graph[curr][i].second;
      // 최단경로라면
      if (dist[curr] - dist[next] == cost)
        for (int j = 0; j < graph[next].size(); j++)
          if (graph[next][j].first == curr) {
            // 간선 제거
            graph[next][j].second = INF;
            // 다음 정점 방문 안했으면 방문처리하고 큐에 추가
            if (!vst[next]) {
              vst[next] = 1;
              q.push(next);
            }
            break;
          }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  while (1) {
    // 그래프 초기화
    for (int i = 0; i < N; i++) {
      graph[i].clear();
      reverse_graph[i].clear();
    }
    cin >> N >> M;
    if (!(N + M))
      break;
    cin >> S >> D;
    // 간선 입력
    while (M--) {
      int u, v, w;
      cin >> u >> v >> w;
      graph[u].push_back({v, w});
      // 역 추적 그래프
      reverse_graph[v].push_back({u, w});
    }
    // 최단 경로
    dijkstra(S, D);
    // 최단 경로 제거
    bfs();
    // 거의 최단 경로
    int ans = dijkstra(S, D);
    cout << (ans == INF ? -1 : ans) << '\n';
  }
  return 0;
}