[백준 1833번] 고속철도 설계하기 (C++)

문제링크 : https://www.acmicpc.net/problem/1833

1833번: 고속철도 설계하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

struct p
{
    int u, v, weight;
    bool operator<(p const &e) 
    {
        return weight < e.weight;
    }
};

int parent[201];
vector<p>edge;

int find_root(int x) //부모찾기
{
    if(x == parent[x]) return x;
    return parent[x] = find_root(parent[x]);
}

bool check(int a, int b) //이어졌는가?
{
    a=find_root(a);
    b=find_root(b);
    if(a==b) return 1;
    return 0;
}

void Union(int a, int b) //병합
{
    a=find_root(a);
    b=find_root(b);
    parent[b]=a;
}

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

    int N, result = 0;
    cin >> N;

    for(int i=1; i<=N; i++) parent[i] = i;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            int cost;
            cin >> cost;
            if (i<j && cost<0) //가중치가 음수라면 이미 연결되어있으므로 더해줌
            {
                Union(i, j);
                result+=abs(cost);
            }
            else if(cost > 0)edge.push_back({i, j, cost});
        }
    }

    vector<pii>ans; //새로 고속도로가 설치된 두 도시번호
    sort(edge.begin(), edge.end()); //비용이 저렴한 순으로 정렬
    for(int i=0; i<edge.size(); i++)
    {
        int x = edge[i].u;
        int y = edge[i].v;
        if(check(x,y)) continue; //이어져있으면 패스
        Union(x, y); //이어주기
        result+=edge[i].weight; //비용 추가
        ans.push_back({x, y}); //이어진 두 도시번호 저장
    }

    cout << result << " " <<ans.size() << "\n"; //총 비용, 설치한 고속철도의 개수
    for(auto [x, y] : ans)
    {
        cout << x << " " << y << "\n"; //각 도시 정보 출력
    }
    
    return 0;
}

가중치가 있는 최소 신장 그래프를 만드는 크루스컬 알고리즘의 다소 변형된 문제이다.

 

분리집합 문제에서 사용했던 유니온 파인드 알고리즘을 사용한다.

 

가중치가 음수라면 이미 연결되어있는 상태이므로 비용에 더해주고 Union을 해준다.

비용이 0인 것은 자기 자신의 위치이므로 비용이 0보다 큰 값에 대해서 도시 정보와 비용을 저장한다.

여기서 가중치가 음수인것 뿐만이 아니라 i<j에 대해서만 해주는 것은 중복방지를 위해서다.

i=1, j=3에 대해서 이미 유니온과 결과값을 담았는데, i=3, j=1은 이어진 것은 똑같은데 비용을 또 더해줌으로써 비용 중복이 발생하기 때문이다.

그래서 중복 방지를 위해 i<j이나 i>j을 넣어주어야 한다.

여기서 i<=j이나 i>=j을 해주어도 정답처리되는데 i==j인 경우는 비용이 0이기 때문이다.

이런 경우는 cost=0인 경우의 예외처리를 미리 해준 것이므로 아래 else if(cost>0)을 할 필요 없이 else만 써도 된다.

 

이후 비용이 저렴한 순으로 정렬을 해주고 해당 벡터에 대해 탐색을 시작한다. (최소비용이 되도록)

각 도시 정보에 대해서 이미 이어져있다면 넘기고, 이어져 있지 않은 것에 대해 Union을 해주고 해당 비용을 더해준다.

그리고 이렇게 이어진 도시는 따로 result에 저장해준다.

이를 모든 도시들이 이어질때까지 반복하게 된다.