백준(BOJ) 16398 행성연결 C++ 풀이

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

16398번: 행성 연결

 

모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다.

 

개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다.

 

효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 신장 트리로 풀 수 있다고 판단하였다.

 

MST와 관련된 알고리즘은 Kruskal, Prim 알고리즘이 있으며 Kruskal을 이용하여 풀이를 진행하였다.

 

신장 트리는 그래프에서 간선을 제거하여 만드는 트리이므로 싸이클이 발생하지 않아야 한다. 트리를 구성하는 노드 집함에 새로운 노드를 추가할 때, 그 노드로 인해 싸이클이 발생하는 지 판단하기 위해서는 Union-Find 개념을 알아야 한다.

 

문제 풀이 소스코드:

/* BOJ 16938 행성 연결 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
#include <cstring>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, p[1001], arr[1001][1001];
vector<pair<pair<int, int>, int>> edges;
 
int find_parent(int x)
{
    if (p[x] != x)
        p[x] = find_parent(p[x]);
 
    return p[x];
}
 
void union_parent(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
 
    if (a > b)
        p[a] = b;
    else p[b] = a;
}
 
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    if (p1.second == p2.second)
        return p1.first.first < p1.first.first;
    else
        return p1.second < p2.second;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            {
                cin >> arr[i][j];
                if (i > j) // 양방h 간선이므로, 중복되는 간선은 제외하고 edges에 삽입
                    edges.push_back({ {i, j}, arr[i][j] });
            }
        }
 
    for (int i = 1; i <= n; i++) // 부모 배열 초기화
        p[i] = i;
    
    sort(edges.begin(), edges.end(), cmp); // 간선의 (비용 기준) 오름차순 정렬
 
    ll ans = 0;
    for (auto edge : edges) // 정렬된 간선 집합에서 간선을 하나씩 빼온다
    {
        // 사이클이 없어야함
        if (find_parent(p[edge.first.first]) != find_parent(p[edge.first.second]))
        {
            union_parent(p[edge.first.first], p[edge.first.second]); // 사이클이 없다면 하나의 집합으로 합치고
            ans += edge.second; // 그 때의 비용을 더한다. -> 가장 효율적인 flow 건설 비용을 구하는 과정
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

 

먼저, 문제에서 주어지는 arr 배열은 양방향 간선으로 구성된 대칭행렬이다. 따라서 동일한 간선을 두 번 edges 벡터에 추가할 필요 없으므로 i >j 일 때만 edges라는 벡터에 삽입하도록 한다. 이 때 해당 간선 양 끝의 노드도 함께 벡터에 저장한다.

 

간선의 비용을 기준으로 오름차순 정렬한 후에는, edges 벡터에서 원소 edge를 하나씩 꺼내고, 해당 간선 양 끝의 노드가 같은 집합에 포함되어 있지 않다면(find) 두 노드를 신장 트리에 포함시킨다.(union) 그리고 그 때의 간선 길이를 신장 트리 구성 간선 길이에 더하도록 한다.

 

한 가지 주의할 점으로, 행성이 1000개인데 비용의 최대값이 100000000이므로 int로 ans를 선언하면 오답이 된다. 이 경우에는 더 큰 값을 수용할 수 있는 long long 타입을 이용하여 선언해야 정답 처리를 받을 수 있을 것이다.

 

(본 포스팅에서, 가중치 == 간선 길이 == 비용입니다.)