[백준 / BOJ] C++ 23034 조별과제 멈춰!

23034번: 조별과제 멈춰!

 

문제

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

23034번: 조별과제 멈춰!

 

 

풀이

처음에는 X, Y 정점부터 시작하는 최소 스패닝 트리(MST)를 구해줬는데 당연히 시간초과를 받았다. 그래서 생각한 다음 방법은 처음부터 MST를 구해놓은 다음 X와 Y 사이의 가장 큰 가중치를 가지는 간선을 제거해 주는 방법이었다.

 

처음에는 MST의 간선을 이을 때마다 어느 정점에서 이어졌는지를 기록하고 역추적하는 방식으로 구현했다. 그러나 여전히 시간복잡도는 컸기 때문에 이 방법은 포기했다. 다음으로 MST를 이루는 간선에 대해 BFS를 통해 시작 정점부터 각 정점까지의 간선 중 가중치가 가장 큰 간선의 가중치를 기록했다.

 

따라서 2차원 배열 dist를 만들고 BFS의 큐에 (현재 노드, 현재 노드까지의 간선 중 MAX 가중치)를 pair로 넣어주고 현재 노드와 이어진 간선들에 대해 MAX 가중치와 간선의 가중치 중 더 큰 값을 저장하도록 하며 진행했다.

 

그런 다음, 각 질문에 대해 X, Y를 입력받고 MST의 가중치 - dist[X][Y]를 출력해 줬다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define piii pair<int, pii>

int V, E, Q;
vector<piii> edges[1001]; // 모든 간선들
vector<pii> mst_edges[1001]; // MST를 이루는 간선들
vector<vector<int>> dist(1001, vector<int>(1001, -1)); // MST 위의 정점->정점 중 최대 가중치

// 프림 알고리즘 MST
int prim() {
  priority_queue<piii> pq;
  vector<int> visited(V + 1, 0);
  visited[1] = 1;
  for (piii edge : edges[1])
    pq.push(edge);
  int cost = 0, cnt = 1;
  while (cnt < V) {
    int weight = -pq.top().first; // 가중치
    int node = pq.top().second.first; // 다음 노드
    int curr = pq.top().second.second; // 현재 노드
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      cost += weight;
      cnt++;
      // MST를 이루는 간선 추가 (다음노드, 가중치) (양방향)
      mst_edges[curr].push_back({node, weight});
      mst_edges[node].push_back({curr, weight});
      for (piii next : edges[node])
        if (!visited[next.second.first])
          pq.push(next);
    }
  }
  return cost;
}

// MST 위에서 정점 사이의 최대 가중치 간선 구하기
void bfs(int s) {
  queue<pii> q;
  dist[s][s] = 0; // 자기 자신으로는 0
  q.push({s, 0});
  while (!q.empty()) {
    auto [curr, maxWeight] = q.front(); // 현재노드, 현재까지 최대가중치
    q.pop();
    // 현재 노드와 연결된 MST를 이루는 간선들에 대해
    for (auto [next, weight] : mst_edges[curr])
      // 아직 시작노드와 연결되지 않았으면
      if (dist[s][next] == -1) {
        int tmp = max(maxWeight, weight); // max(현재까지 최대가중치, 이번 가중치)
        dist[s][next] = tmp;
        q.push({next, tmp});
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> V >> E;
  while (E--) {
    int a, b, c;
    cin >> a >> b >> c;
    // 간선 (가중치, 다음노드, 현재노드)
    edges[a].push_back({-c, {b, a}});
    edges[b].push_back({-c, {a, b}});
  }
  int mst = prim(); // 최소 스패닝 트리의 가중치
  // MST의 간선 중에서 한 정점에서 각 정점까지의 간선 중 가중치가 가장 큰 값
  for (int i = 1; i <= V; i++)
    bfs(i);
  cin >> Q;
  while (Q--) {
    int X, Y;
    cin >> X >> Y;
    // MST의 가중치 - (X -> Y로의 간선 중 가장 큰 가중치)
    cout << mst - dist[X][Y] << '\n';
  }
  return 0;
}