지배 집합(Dominating Set)은 그래프 이론에서 잘 알려진 NP-난해(NP-Hard) 문제입니다. 그래프가 주어졌을 때, 그래프의 모든 정점이 이 집합에 직접 속하거나 집합에 속한 어떤 정점과 인접해 있도록 만드는 최소 크기의 정점 집합을 찾는 것이 목표입니다.
아래는 지배 집합 문제를 해결하기 위한 C++ 프로그램입니다. 이 프로그램은 탐욕적(greedy) 기법을 활용하여 근사 해를 빠르게 구합니다.
알고리즘
시작
정점의 개수와 간선의 개수를 입력받고, 각 간선의 양 끝점도 함께 입력받습니다.
dominant() 함수:
벡터 Set을 선언합니다.
두 정점 X와 Y를 연결하는 임의의 간선 e를 선택합니다.
X와 Y 중 하나의 정점을 집합 s에 추가합니다.
X에 연결된 모든 간선을 제거합니다.
종료예제 코드
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool visit[10001];
int i,j;
vector<int> dominant(int v,int e) {
vector<int> Set;
//두 정점 X와 Y를 연결하는 임의의 간선 e를 선택합니다.
for(i=0;i<v;i++) {
if(!visit[i]) {
Set.push_back(i); //정점 추가
visit[i]=true;
for(j=0;j<(int)g[i].size();j++) {
if(!visit[g[i][j]]) {
visit[g[i][j]]=true;
break;
}
}
}
}
return Set;
}
int main() {
int v,e,a,b;
cout<<"정점의 개수 입력:";
cin>>v;
cout<<"간선의 개수 입력:";
cin>>e;
g.resize(v);
memset(visit,0,sizeof(visit)); //배열의 모든 인덱스 값을 0으로 초기화
for(i=0;i<e;i++) {
cout<<"간선 "<<i+1<<"의 양 끝점 입력 : ";
cin>>a>>b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> Set = dominant(v,e);
cout<<"지배 집합은 다음과 같습니다:\n";
for(i=0;i<(int)Set.size();i++)
cout<<Set[i]+1<<" ";
return 0;
}실행 결과
정점의 개수 입력:7 간선의 개수 입력:6 간선 1의 양 끝점 입력 : 1 2 간선 2의 양 끝점 입력 : 2 2 간선 3의 양 끝점 입력 : 3 4 간선 4의 양 끝점 입력 : 4 5 간선 5의 양 끝점 입력 : 6 7 간선 6의 양 끝점 입력 : 4 5 지배 집합은 다음과 같습니다: 1 3 5 6
코드 동작 원리
이 프로그램은 인접 리스트(adjacency list) 형태의 2차원 벡터 g에 그래프 정보를 저장합니다. 사용자로부터 정점 수, 간선 수, 그리고 각 간선의 양 끝점을 입력받은 뒤 무방향 그래프를 구성합니다.
dominant() 함수는 모든 정점을 순회하면서 아직 방문하지 않은 정점을 발견하면 해당 정점을 결과 집합에 추가하고, 그 정점에 인접한 미방문 정점 하나를 함께 방문 처리합니다. 이 과정을 반복하면 그래프 전체를 커버하는 지배 집합이 완성됩니다.
마지막으로 main() 함수에서 완성된 지배 집합의 정점 번호(1부터 시작하는 번호 체계)를 출력합니다. 위 실행 예제에서는 7개의 정점과 6개의 간선으로 구성된 그래프에 대해 {1, 3, 5, 6}이라는 지배 집합을 얻었습니다.