개념
주어진 무방향 그래프에서 크기 l의 독립 집합(independent set)이 존재하는지 확인하는 문제입니다. 독립 집합이 존재하면 'Yes'를 출력하고, 존재하지 않으면 'No'를 출력합니다. 여기서 독립 집합이란 집합에 속한 어떤 두 정점도 서로 직접 연결(간선으로 이어져 있지 않은)되어 있지 않은 정점들의 집합을 의미합니다.
입력 예시 1
L = 4, graph = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]];
출력
Yes
위 그래프는 크기 4의 독립 집합을 포함합니다. 정점 0, 1, 3, 4는 서로 직접 연결되어 있지 않으므로 출력은 'Yes'입니다.
입력 예시 2
L = 4, graph = [[1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]];
출력
No
위 그래프에는 크기 4의 독립 집합이 존재하지 않습니다. 따라서 출력은 'No'입니다.
풀이 방법
- 먼저 sol 변수를 false 값으로 초기화합니다.
- 주어진 그래프에서 크기 L이 될 수 있는 모든 정점 조합을 생성합니다.
- 크기 l의 독립 집합을 찾으면 sol 값을 true로 변경한 뒤 탐색을 종료합니다.
- 아직 찾지 못했다면 나머지 가능한 조합을 계속 검사합니다.
- 마지막에 sol이 true이면 'Yes'를, 그렇지 않으면 'No'를 출력합니다.
이 방식은 가능한 모든 정점 조합을 검사하는 완전 탐색(brute force) 기법입니다. 정점 수가 n일 때 최악의 경우 O(2n × n²)의 시간이 소요될 수 있어 정점이 많은 그래프에는 비효율적이지만, 독립 집합 판정 문제의 핵심 원리를 명확하게 보여주는 접근 방식입니다.
C++ 구현 예제
// C++ 코드: 주어진 그래프가
// 크기 k의 독립 집합을 포함하는지 확인
#include <bits/stdc++.h>
using namespace std;
// 함수 원형 선언
bool check1(int[][5], vector<int>&, int);
// 주어진 크기 l의 집합을 구성하는 함수
bool func(int graph1[][5], vector<int>&arr1,
int l, int index1, bool sol1[]){
// 선택된 집합이 독립 집합인지 확인.
// 독립 집합이라면 sol 값을 true로 바꾸고 반환
if (l == 0){
if (check1(graph1, arr1, arr1.size())){
sol1[0] = true;
return true;
}
}
else{
// 현재 인덱스의 정점을 포함하지 않아도
// 크기 l의 집합을 만들 수 있는 경우
if (index1 >= l){
vector<int> newvec(arr1.begin(), arr1.end());
newvec.push_back(index1);
return (func(graph1, newvec, l - 1,
index1 - 1, sol1) or
func(graph1, arr1, l, index1 - 1, sol1));
}
// 현재 인덱스의 정점을 포함하지 않으면
// 크기 l의 집합을 만들 수 없는 경우
else{
arr1.push_back(index1);
return func(graph1, arr1, l - 1,
index1 - 1, sol1);
}
}
}
// 주어진 집합이 독립 집합인지
// 검사하는 함수
// arr --> 크기 l의 집합 (포함된 정점의
// 인덱스를 저장)
bool check1(int graph1[][5], vector<int>&arr1, int n1){
// 집합 내 각 정점이 다른 정점과
// 연결되어 있는지 확인
for (int i = 0; i < n1; i++)
for (int j = i + 1; j < n1; j++)
if (graph1[arr1[i]][arr1[j]] == 1)
return false;
return true;
}
// 드라이버 코드
int main(){
int graph1[][5] = {{1, 0, 1, 0, 0},{0, 1, 1, 0, 0},{1, 1, 1, 1, 1},{0, 0, 1, 1, 0},
{0, 0, 1, 0, 1}};
int l = 4;
vector<int> arr1; // 빈 집합
bool sol1[] = {false};
int n1 = sizeof(graph1) /
sizeof(graph1[0]);
func(graph1, arr1, l, n1 - 1, sol1);
if (sol1[0])
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}실행 결과
Yes
코드 설명
func 함수는 재귀적으로 크기 l의 정점 집합을 구성합니다. 현재 인덱스의 정점을 집합에 포함하는 경우와 포함하지 않는 경우를 모두 탐색하며, 남은 정점 수만으로는 목표 크기를 채울 수 없을 때는 반드시 현재 정점을 포함하도록 하여 불필요한 탐색을 줄입니다.
check1 함수는 선택된 정점들 사이에 간선이 하나라도 존재하는지 검사합니다. 인접 행렬에서 해당 위치의 값이 1이면 두 정점이 연결된 것이므로 독립 집합이 아니며 false를 반환합니다. 모든 정점 쌍이 서로 연결되어 있지 않다면 true를 반환하여 유효한 독립 집합임을 알립니다.