Degree Bounded Minimum Spanning Tree( BOJ 20927 )

문제 : https://www.acmicpc.net/problem/20927

20927번: Degree Bounded Minimum Spanning Tree

 

문제 파악하기

N개의 정점을 모두 연결하는 트리 중 가중치의 값이 가장 작은 트리의 모양을 찾는 문제입니다. 얼핏 보면 Spanning Tree 알고리즘 문제처럼 보이지만 이 문제는 한 가지 조건이 더 주어집니다. 바로 각각의 노드가 가질 수 있는 차수가 제한되어 있습니다. 그렇기에 기존의 크루스칼 혹은 프림 알고리즘을 사용할 수 없습니다. 하지만, 다행히 정점과 간선의 개수가 적기에 우리는 완전탐색을 할 수 있습니다.

 

문제 해결하기

간선의 개수와 정점의 개수가 특히 적기 때문에 우리는 완전탐색을 통해 트리의 모양을 찾을 수 있습니다. 각각의 간선을 사용한 경우와 사용하지 않은 경우로 나눠서 탐색을 진행한 다음, (N-1)개의 간선을 선택했다면 탐색을 종료하고 우리가 원하는 조건을 만족하는지 확인하면 됩니다. 여기서 확인할 점은 크게 2가지 입니다. 첫 번째, 현재 간선 때문에 cycle이 생겼는지 확인해야 합니다. cycle이 생겼다는 건 트리의 모양이 아니라는 뜻이기 때문에 해당 경우는 제외해야하며, 확인하기 위해서는 Union-find 연산을 사용하면 됩니다. 두 번째, 현재 간선 때문에 정점의 차수 제한을 위반했는지 확인해야 합니다. 각각의 정점은 차수 제한이 있기 때문입니다. 2가지에 주의해서 검사하면 우리는 원하는 결괏값을 얻을 수 있습니다. 이번 문제는 시간 제한도 3초로 넉넉하기 때문에 완전탐색 알고리즘만 섬세하게 설계한다면 어렵지 않게 풀 수 있습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <vector>
#define NMAX 15
#define INF 0x7FFFFFFF
#define PAIR pair< int, int >
using namespace std;
 
struct Inp {
    int st, ed, cost;
};
 
int N, M;
int S, E, C;
int B[NMAX];
vector< Inp > inp;
 
int vmin;
int curB[NMAX], parent[NMAX];
vector< PAIR > tmp, ret;
 
int find(int p) {
    if(parent[p] == p) return p;
    else return parent[p] = find(parent[p]);
}
 
bool isPossible(vector< PAIR > Edges) {
    int pa, pb;
 
    // cycle 여부 확인
    for(int i=1;i<=N;i++) parent[i] = i;
    for(PAIR p:Edges) {
        pa = find(p.first);
        pb = find(p.second);
 
        if(pa == pb) return 0;
        else parent[pa] = pb;
    }
 
    return 1;
}
 
void sv(int idx, int val, vector< PAIR > Edges) {
    // 종료 조건
    if(Edges.size() == N-1) {
        if(isPossible(Edges) and val < vmin) {
            vmin = val;
            ret = Edges;
        }
 
        return;
    }
    else if(idx == M) return;
 
    // 현재 간선을 사용하지 않는 경우
    sv(idx+1, val, Edges);
 
    // 현재 간선을 사용한 경우
    int st, ed;
    st = inp[idx].st; ed = inp[idx].ed;
    if(curB[st] < B[st] and curB[ed] < B[ed]) {
        curB[st]++; curB[ed]++;
        Edges.push_back({inp[idx].st, inp[idx].ed});
 
        sv(idx+1, val+inp[idx].cost, Edges);
 
        curB[st]--; curB[ed]--;
    }
}
 
int main() {
    // 입력
    scanf("%d %d", &N, &M);
    for(int i=1;i<=N;i++) scanf("%d", &B[i]);
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &S, &E, &C);
 
        inp.push_back({S, E, C});
    }
 
    // 완전탐색
    vmin = INF;
    for(int i=1;i<=N;i++) parent[i] = i;
 
    sv(0, 0, tmp);
 
    // 출력
    if(vmin == INF) printf("NO");
    else {
        printf("YES\n");
        for(PAIR p:ret) printf("%d %d\n", p.first, p.second);
    }
}
/*
5 6
3 3 3 2 2
1 2 1
1 3 3
2 4 2
2 3 3
1 5 2
3 5 5
ans
1 2
2 4
2 3
1 5
*/

후기

문제의 조건만 잘 지킨다면 구현이 크게 어렵지 않은 문제입니다. 다만 완전탐색을 하는 방법을 연습하는 사람에게는 그리 쉬운 문제는 아니라고 생각합니다. 완전 탐색(브루트포스)를 연습하는 사람에게 추천하고 싶은 문제입니다.