BOJ 1833 - 고속철도 설계하기 링크
(2023.07.03 기준 G3)

문제

N개의 도시와 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다.
비용이 음수이면 이미 설치된 경우라고 했을 때, 고속철도를 추가로 설치하여 모든 도시가 이어지게끔 드는 최소 비용와 새로 설치하는 고속철도의 개수 및 정보 출력

알고리즘

MST

풀이

일단 모든 도시가 최소 비용으로 이어지게끔 하는 것은 MST다.
근데 이 문제는 이미 설치된 도로. 즉, 두 정점이 연결되어 있는 간선이 이미 여러 개가 있다.
그리고 새로 설치하는 고속철도의 개수가 필요하다.

그럼 일단 C를 정확하게 보자. C는 고속철도망을 설치하는데 든 총 비용이다. 이 문장이 좀 애매할 수 있는데, 결론은 이미 설치된 고속철도의 비용을 합한 총 비용이다.
그러므로 처음에 인접행렬을 이용하여 간선 정보를 저장할 때, 비용이 양수면 그대로, 비용이 음수면 비용을 0으로 하여 간선을 저장한 뒤, C에 그 비용의 절댓값을 더해주자.

그리고 여느 MST 문제와 같이 크루스칼을 이용하여 간선의 총 개수가 N - 1개가 될 때까지 union-find를 하면 된다. 이 때, 당연히 비용이 양수여야 새로 설치하는 도로다.

코드

• C++

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

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int pa[200];

int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

void merge(int u, int v){
    u = find(u); v = find(v);

    if (u < v) pa[v] = u;
    else pa[u] = v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int matrix[N][N];
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> matrix[i][j];

    vector<tiii> edges;
    int C = 0; // 고속철도망의 총 비용
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++){
        if (matrix[i][j] > 0) // 양수면 설치 가능한 도로
            edges.push_back({matrix[i][j], i, j});
        else{ // 음수면 이미 설치되어 있는 도로
            edges.push_back({0, i, j}); // 간선의 비용은 0으로 잡고
            C -= matrix[i][j]; // 설치 비용을 총 비용에 더하자.
        }
    }

    sort(edges.begin(), edges.end()); iota(pa, pa + N, 0); // 간선 정렬 및 부모 초기화
    int M = 0, ct = 0; // 새로 설치하는 도로 수, 연결된 간선 수
    vector<pii> result; // 새로 설치하는 도로 저장
    for (auto [w, u, v]: edges) if (find(u) != find(v)){ // 부모가 다르면 union
        merge(u, v);
        if (w) // 간선의 비용이 양수면 새로 설치하게 되는 도로다.
            C += w, M++, result.push_back({u + 1, v + 1});
        if (++ct == N - 1) break; // 연결된 간선 수가 N - 1개면 MST 완성이므로 중지
    }

    cout << C << ' ' << M << '\n';
    for (auto [u, v]: result) cout << u << ' ' << v << '\n';
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

def union(u, v):
    u = find(u); v = find(v)

    if u < v:
        pa[v] = u
    else:
        pa[u] = v

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]

edges = []
C = 0 # 고속철도망의 총 비용
for i in range(N - 1):
    for j in range(i + 1, N):
        if matrix[i][j] > 0: # 양수면 설치 가능한 도로
            edges.append((matrix[i][j], i, j))
        else: # 음수면 이미 설치되어 있는 도로
            edges.append((0, i, j)) # 간선의 비용은 0으로 잡고
            C -= matrix[i][j] # 설치 비용을 총 비용에 더하자.

pa = [i for i in range(N)] # 부모
M = ct = 0 # 새로 설치하는 도로 수, 연결된 간선 수
result = [] #  새로 설치하는 도로 저장
for w, u, v in sorted(edges):
    if find(u) != find(v): # 부모가 다르면 union
        union(u, v)
        if w: # 간선의 비용이 양수면 새로 설치하게 되는 도로다.
            C += w
            M += 1
            result.append((u + 1, v + 1))
        ct += 1
        if ct == N - 1: # 연결된 간선 수가 N - 1개면 MST 완성이므로 중지
            break

print(C, M)
for u, v in result:
    print(u, v)