Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 그래프에서 감소할 수 있는 최대 점수 찾기

문제 개요

n개의 정점과 m개의 간선으로 이루어진 가중치 무방향 그래프가 있다고 가정해 보겠습니다. 그래프의 점수(score)는 그래프에 포함된 모든 간선 가중치의 합으로 정의됩니다. 간선의 가중치는 음수일 수도 있는데, 음수 가중치를 가진 간선을 제거하면 오히려 점수가 증가하게 됩니다.

우리가 해야 할 작업은 그래프의 연결 상태를 유지하면서 간선을 제거해 그래프의 점수를 최소화하는 것이며, 이때 감소시킬 수 있는 점수의 최댓값을 구하는 것입니다.

입력 형식과 예시

그래프는 'edges' 배열로 주어지며, 각 원소는 {weight, {vertex1, vertex2}} 형태를 가집니다. 첫 번째 값은 간선의 가중치이고, 두 번째 값은 간선이 연결하는 두 정점입니다.

예를 들어 다음과 같은 입력이 주어졌다고 해보겠습니다.

n = 5, m = 6
edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}

C++ 그래프에서 감소할 수 있는 최대 점수 찾기

이 경우 출력은 4가 됩니다. 그래프에서 간선 (1, 2)와 (2, 5)를 제거하면 점수가 총 4만큼 감소하면서도 그래프는 여전히 연결 상태를 유지하기 때문입니다.

해결 접근 방법

이 문제는 크루스칼(Kruskal) 알고리즘과 유니온-파인드(Union-Find) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 그래프가 연결 상태를 유지하려면 최소 신장 트리(MST)를 구성하는 간선은 반드시 남겨야 하고, 그 외의 간선 중 가중치가 양수인 것들은 모두 제거해 점수를 낮출 수 있습니다.

알고리즘의 진행 과정은 다음과 같습니다.

  1. 연결 요소의 개수를 나타내는 cnum을 n으로 초기화하고, 각 정점 v에 대해 make(v)를 호출해 부모 배열(par)과 집합의 크기(dim)를 초기화합니다.
  2. 간선 배열을 가중치를 기준으로 오름차순 정렬합니다.
  3. 결괏값 res를 0으로 초기화한 뒤, 정렬된 간선을 하나씩 살펴봅니다.
    • 두 정점 a, b가 이미 같은 집합에 속해 있다면 이 간선은 사이클을 형성하는 간선이므로 연결성에 필수적이지 않습니다. 따라서 제거할 수 있으며, 가중치가 0 이상이면 res에 가중치를 더합니다.
    • cnum이 1이라면 그래프가 이미 하나의 연결 요소로 묶인 상태이므로, 이 간선을 제거해도 연결성이 유지됩니다. 마찬가지로 가중치가 0 이상이면 res에 더합니다.
    • 위 두 경우에 해당하지 않으면 unify(a, b)를 호출해 두 정점을 같은 집합으로 합칩니다. 이때 cnum이 1씩 감소합니다.
  4. 모든 간선을 처리한 후 res를 반환합니다. 이 값이 바로 감소시킬 수 있는 점수의 최댓값입니다.

예제 코드

다음 C++ 구현을 통해 더 잘 이해해 보겠습니다.

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

int cnum = 0;
int par[100];
int dim[100];

void make(int v){
    par[v] = v;
    dim[v] = 1;
}
int find(int v){
    if(par[v] == v)
        return v;
    return par[v] = find(par[v]);
}
void unify(int a, int b){
    a = find(a); b = find(b);
    if(a != b){
        cnum--;
        if(dim[a] > dim[b]){
            swap(a, b);
        }
        par[a] = b; dim[b] += dim[a];
    }
}
int solve(int n, int m, vector <pair <int, pair<int,int>>> edges){
    cnum = n;
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= n; i++)
        make(i);
    int res = 0;
    for(auto &edge : edges){
        int a = edge.second.first;
        int b = edge.second.second;
        int weight = edge.first;
        if(find(a) == find(b)) {
            if(weight >= 0)
                res += 1 * weight;
            continue;
        }
        if(cnum == 1){
            if(weight >= 0)
                res += 1 * weight;
        } else {
            unify(a, b);
        }
    }
    return res;
}
int main() {
    int n = 5, m = 6;
    vector <pair<int, pair<int,int>>> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}};
    cout << solve(n, m, edges);
    return 0;
}

입력

5, 6, {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}

출력

4

복잡도 분석

간선 정렬에 O(m log m)의 시간이 걸리고, 유니온-파인드 연산은 경로 압축과 크기 기반 합치기 기법 덕분에 사실상 선형 시간에 처리되므로, 전체 시간 복잡도는 O(m log m)입니다.