집합 커버 문제 Set Cover Problem

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}

 

정답은, 가장 많은 노드를 커버하는 순서대로 4, 6, 1이 정답이 된다.

 

---

SetCover Problem Pseudo Code

 

입력: U, F={Si}, i=1,⋯,n 

출력: 집합 커버 C

 

1. C=∅ // 모든 노드를 커버하는 노드 집합

2. while (U≠∅) do // 모든 노드를 방문할 때까지 반복 
{ 
    3. U의 원소들을 가장 많이 포함하고 있는 집합 S(i)를 F에서 선택
    4. U=U-S(i) // 선택한 S(i)를 뺀다
    5. S(i)를 F에서 제거하고, S(i)를 C에 추가한다.
}
6. return C

 

// 수도코드 2번

int checkEmpty()
{
    // 모든 U의 요소들이 0인지 확인한다.
    // 즉 모든 노드를 커버한다면 0, 아직 남아있다면 1
    for(int i = 0; i < 10; i++)
    {
        if(U[i] == 1)
            return 1;
    }

    return 0;
}

 

// 수도코드 3번

int getMaxCover(Node* node)
{
    int max = 0;
    int maxIndex = -1;
    int count = 0;
    
    // S[i]가 커버하는 노드의 갯수를 count에 저장하고
    // 가장많이 커버하는 maxIndex를 구한다.
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            if(U[j] == 1 && node->S[i][j] == 1)
                count++;
        }

        if(max < count)
        {
            max = count;
            maxIndex = i;
        }
        count = 0;
    }

    return maxIndex;
}

void setCover(Node* node)
{
    // U가 안비었을 때 동작, 아직 모든 노드를 커버하지 못할 때 동작
    while(checkEmpty()) // 수도코드의 2번
    {
    	// 가장 많은 노드를 커버하는 인덱스를 찾음
        int maxIndex = getMaxCover(node); // 수도코드의 3번

        if(maxIndex != -1){
            // 가장 많은 노드를 커버하는 maxIndex를 C에 추가
            C[maxIndex] = 1; // 수도코드의 3번
        }

        // 가장 많은 노드를 커버하는 인덱스를 U에서 삭제함
        removeIndex(node,maxIndex);
    }

    printf("\nSet Cover End\n");

    // 결과 출력
    int first = 0;
    printf("C = {");
    for(int i = 0; i < 10; i++)
    {
        if(C[i] == 1)
        {
            if(first == 1)
                printf(", ");
                first = 1;
            printf("S%d ", i+1);
        }
    }
    printf("}\n");
}

// 수도코드의 4번

void removeIndex(Node* node,int i)
{
    // S[i]를 선택했으니 S[i]가 커버하는 곳을 U에서 제거
    for(int j = 0; j < 10; j++)
    {
        if(node->S[i][j] == 1 && U[j] == 1)
        {
            U[j] = 0;
        }
    }
}

 

전체코드

#include <stdio.h>
#include <stdlib.h>

int C[10] = {0,0,0,0,0,0,0,0,0,0};
int U[10] = {1,1,1,1,1,1,1,1,1,1};

typedef struct Node{
    int S[10][10];
}Node;

// 수도코드 2번
int checkEmpty()
{
    // 모든 U의 요소들이 0인지 확인한다.
    // 즉 모든 노드를 커버한다면 0, 아직 남아있다면 1
    for(int i = 0; i < 10; i++)
    {
        if(U[i] == 1)
            return 1;
    }

    return 0;
}

// 수도코드의 4번
void removeIndex(Node* node,int i)
{
    // S[i]를 선택했으니 S[i]가 커버하는 곳을 U에서 제거
    for(int j = 0; j < 10; j++)
    {
        if(node->S[i][j] == 1 && U[j] == 1)
        {
            U[j] = 0;
        }
    }
}

// 수도코드 3번
int getMaxCover(Node* node)
{
    int max = 0;
    int maxIndex = -1;
    int count = 0;
    
    // S[i]가 커버하는 노드의 갯수를 count에 저장하고
    // 가장많이 커버하는 maxIndex를 구한다.
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            if(U[j] == 1 && node->S[i][j] == 1)
                count++;
        }

        if(max < count)
        {
            max = count;
            maxIndex = i;
        }
        count = 0;
    }

    return maxIndex;
}

void printNode(Node node)
{
    for(int i = 0; i < 10; i++)
    {
        printf("S%d = {",i+1);
        int first = 0;
        for(int j = 0; j < 10; j++)
        {
            if(node.S[i][j] == 1)
            {
                if(first == 1)
                    printf(", ");
                first = 1;
                printf("%d",j+1);
            }
        }
        printf("}\n");
    }

}

void setCover(Node* node)
{
    // U가 안비었을 때 동작, 아직 모든 노드를 커버하지 못할 때 동작
    while(checkEmpty()) // 수도코드의 2번
    {
    	// 가장 많은 노드를 커버하는 인덱스를 찾음
        int maxIndex = getMaxCover(node); // 수도코드의 3번

        if(maxIndex != -1){
            // 가장 많은 노드를 커버하는 maxIndex를 C에 추가
            C[maxIndex] = 1; // 수도코드의 3번
        }

        // 가장 많은 노드를 커버하는 인덱스를 U에서 삭제함
        removeIndex(node,maxIndex);
    }

    printf("\nSet Cover End\n");

    // 결과 출력
    int first = 0;
    printf("C = {");
    for(int i = 0; i < 10; i++)
    {
        if(C[i] == 1)
        {
            if(first == 1)
                printf(", ");
                first = 1;
            printf("S%d ", i+1);
        }
    }
    printf("}\n");
}

int main(int argc, char* argv[])
{

    Node node = {
        {
            {1,1,1,0,0,0,0,1,0,0},
            {1,1,1,1,0,0,0,1,0,0},
            {1,1,1,1,0,0,0,0,0,0},
            {0,1,1,1,1,0,1,1,0,0},
            {0,0,0,1,1,1,1,0,0,0},
            {0,0,0,0,1,1,1,0,1,1},
            {0,0,0,1,1,1,1,0,0,0},
            {1,1,0,1,0,0,0,1,0,0},
            {0,0,0,0,0,1,0,0,1,0},
            {0,0,0,0,0,1,0,0,0,1}
        }
    };

    printNode(node);
    setCover(&node);
}​