집합 커버 문제 (SetCover)

집합 커버 (Set Cover) 문제?
집합 F에서 선택하는 집합들의 수를 최소화하는 문제

신도시를 계획하는 데 있어서 학교 배치의 예

10개의 마을이 신도시에 만들어질 계획이다.
(마을은 그림에서 점 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

2가지 조건이 만족되도록 학교 위치를 선정해야 한다.

• 학교는 마을에 위치해야 한다.
• 등교 거리는 걸어서 15분 이내이어야한다.

이러한 문제를 집합 커버 문제로 변환

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10}

S1 = {1, 2, 3, 8}

S2 = {1, 2, 3, 4, 8}

S3 = {1, 2, 3, 4}

S4 = {2, 3, 4, 5, 7, 8}

S5 = {4, 5, 6, 7}

S6 = {5, 6, 7, 9, 10}

S7 = {4, 5, 6, 7}

S8 = {1, 2, 4, 8}

S9 = {6, 9}

S10 = {6, 10}

이때, 어떤 집합들을 선택해야 그들의 합집합이 U와 같을 수 있을까?

Cover 하는 도시의 수를 기준으로 알고리즘을 짜보고자 했고

그래서 다음과 같은 과정으로 알고리즘을 구현하였다.

이를 C언어 코드로 구현하면

#include <stdio.h>

int main() {
	int u[] = { 1,2,3,4,5,6,7,8,9,10 }; // 원소
	int s[100][100] = { {1,2,3,8}, {1,2,3,4,8}, {1,2,3,4}, {2,3,4,5,7,8}, {4,5,6,7}, {5,6,7,9,10},
		{4,5,6,7}, {1,2,4,8}, {6,9}, {6,10} }; // 집합
	
	int s_each_count[] = { 4,5,4,6,4,5,4,4,2,2 }; // 각 집합마다 원소의 개수
	int chk_s[10] = {0,}; // 집합의 사용여부
	int chk_u[10] = {0,}; // 현재 원소가 얼마나 남았는지 현황
	
	int remove_count; // 제거한 횟수
	int u_count = 10; // 원소의 개수
	int max_index = 0; // 가장 u원소를 많이 지우는 집합의 위치
	int max_count = 0; // 집합 중 가장 제거한 횟수
	int s_size;
	int max_size = 0; // 가장 제거한 횟수가 많은 집합의 원소의 개수

	printf("결과\n\n");
	while (u_count != 0) {
		max_count = 0; 
		max_size = 0;
		max_index = 0;

		for (int i = 0; i < 10; i++) {
			s_size = s_each_count[i]; // 한 집합의 원소 개수
			remove_count = 0;

			if (chk_s[i] == 0) { // 집합이 쓰였는지 확인

				for (int j = 0; j < s_size; j++) {
					if (chk_u[s[i][j] - 1] == 0) {
						remove_count++;
					}
				}

				if (max_count < remove_count) {
					max_count = remove_count;
					max_size = s_size;
					max_index = i;
				} // 현재 집합에서 제거한 개수가 max_count 보다 더 큰 경우 그 집합 정보(제거 횟수, 그 집합의 크기, 그 집합의 위치)를 저장.
			}
		}

		u_count -= max_count; // 전체 원소의 개수 - 가장 큰 제거횟수를 가진 경우 
		chk_s[max_index] = 1; // 그 집합을 사용한 여부를 체크한다.
		printf("S%d ", max_index + 1); // 그 집합을 표시해주고
		for (int j = 0; j < max_size; j++) {
			chk_u[s[max_index][j] - 1] = 1;
		} // 집합에 해당하는 원소를 전체 원소에서 빼준다.
	}

	printf("\n");
	return 0;
}