[백준 / BOJ] C++ 1833 고속철도 설계하기

1833번: 고속철도 설계하기

 

문제

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

1833번: 고속철도 설계하기

 

 

풀이

최소 스패닝 트리(MST) 응용문제다. 주어진 인접 행렬에 따라 (i, j)의 값이 양수이면 간선을 추가하고, 음수라면 이미 연결되어 있는 간선이므로 i와 j를 union 해주고 전체 비용에 비용의 절댓값을 추가해 준다. 그리고 인접 행렬은 같은 값이 2번씩 입력되므로 ÷2를 해주어 미리 연결되어 있는 간선들의 가중치를 구해준다.

 

이제 크루스칼 알고리즘을 사용해 가중치가 작은 간선부터 다른 컴포넌트를 연결시켜 준다. 간선을 연결시켜 주면 가중치를 추가해 주고 간선의 양 끝 점을 배열에 저장한다.

 

이제 모든 간선을 연결하는 데 사용한 비용과 간선을 저장한 배열의 크기를 출력하고 배열의 각 원소를 출력하면 된다.

 

 

코드

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

int N, C = 0, M = 0;
vector<pair<int, pii>> edge;
vector<pii> mst;
vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      int x;
      cin >> x;
      if (x < 0) { // 음수이면
        merge(i, j); // union
        C -= x; // 가중치 추가
      } else {
        edge.push_back({x, {i, j}}); // 간선 추가
      }
    }
  C /= 2; // 인접 행렬이므로 ÷2
  // 크루스칼 알고리즘
  sort(edge.begin(), edge.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      C += weight;
      mst.push_back(path); // 경로 저장
      merge(path.first, path.second);
    }
  cout << C << ' ' << mst.size() << '\n'; // 비용과 새로이 설치한 고속도로 개수
  for (auto [x, y] : mst) // 새로이 설치한 고속도로의 시작-끝
    cout << x << ' ' << y << '\n';
  return 0;
}