알고리즘 과제 #4 (그래프 최소 경로 구하기)

문제 :   무선 센서 네트워크에서 감시 노드들의 집합 구하기 

무선 센서 네트워크에서 센서들은 서로 교신하며 일을 해야 하므로 네트워크 공격에 취약한데 이러한 공격을 막기 위해 보통 사용하는 기법이 행위 기반 탐지이다. 특별한 감시 노드들이 이웃 노드들이 합법적인지를 알기 위해 이웃의 교신을 감청하고, 공격이 탐지되면 경고 메시지를 감시 노드들만으로 이루어진 경로를 따라 관리를 담당하는 싱크 노드로 전달하게 된다. 

무선 센서 네트워크는 그래프 G = (V, E)로 표현할 수 있는 데, 여기서 V는 센서 노드들의 집합이고 E는 통신 링크들의 집합이다. 임의의 노드 u에 대해 A(u)를 u와 인접한 노드들의 집합이라 한다. X를 노드들의 집합이라 할 때 X와 인접한 노드들의 집합 A(X) = A(u)이다. 

싱크 노드를 v1이라하고 감시 노드 수의 상한 K(싱크 노드 제외)가 주어졌을 |A(X)|가 최대가 되는 감시 노드의 집합 X와 A(X)를 구하는 그리디 알고리즘을 작성하라. 단, X 안에 있는 감시 노드들은 모두 연결되어 있다.

예) K = 2이라 할 때 그림 1의 예에서 X = {1, 3, 7}, A(X) = {1, 2, 3, 7, 8, 9, 10} 또는 X = {1, 2, 3}, A(X) = {1, 2, 3, 4, 5, 6, 7}이 된다. 

입력

입력 파일의 이름은 input.txt이다 .여러 개의 테스트 데이터가 입력될 수 있다. 첫째 줄에는 테스트 데이터의 개수가 입력된다. 첫 번째 데이터가 두 번째 줄부터 부터 주어지는데 K가 주어지고,  그 다음 줄에는 노드의 개수 n이 주어지고, 그 다음 n개의 줄에 무선 네트워크의 인접행렬이 주어진다. 같은 방식으로 다음 데이터들이 주어진다.

출력

각 데이터에 대해 X와 A(X)를  두 줄에 출력한다.

입력 예

2 데이터의 개수

2 첫 번째 데이터의 K 값

10 노드의 수

1 1 1 0 0 ..... 인접 행렬

1 1 0 1 1 .....

......

10 두 번째 데이터의 K 값

100 노드의 수

1 0 0 1 1 ...... 인접 행렬

0 0 0 1 0 ......

......

출력 예

1 3 7 

1 2 3 7 8 9 10

1 6 7 13 16 25 37 45 67 88 

1 5 6 7 13 ........

소스코드

#include <iostream> #include <fstream> #define Y 1 //그룹 Y #define V 2 //그룹 V using namespace std; /* 프로그램 작성자 : americano@korea.ac.kr 개발 날짜 : 2012-5-29 */ //노드 정보 typedef struct { int *link; // 링크집합 int value; // 링크수 int group; // 그룹 } Node; typedef Node* Nptr; //그래프 클래스 class NetWork{ private: int K; //감시노드 상한 값 int N; //노드 수 int *K_Array; // 그룹 Y 그래프 Nptr Graph; public: NetWork(int k, int n, Nptr graph); void make_Graph(); //그래프 생성 함수 void modify_Graph(); //중첩된 노드의 링크를 제거하는 함수 int get_MaxGraph(); //다음 노드를 선택해주는 함수 void print(); //출력함수 }; NetWork::NetWork(int k, int n, Nptr graph){ //클래스 초기화 K = k; N = n; Graph = graph; //감시노드의 그래프 : Graph[N] //입력받은 그래프 : Graph[i] (0 <= i < N) for(int i=0; i< N; i++) Graph[N].link[i] = 0; Graph[N].value = 0; //그룹 Y의 그래프 : K_Array[i] (0 <= i < N) K_Array = new int[N]; } void NetWork::make_Graph(){ //그래프 Y와 감시노드그래프 생성함수 for(int i=0; i<K; i++){ int max = get_MaxGraph(); //다음 노드번호를 받아서 K_Array[max] = 1; //그룹 Y에 연결해주고 Graph[N].value += Graph[max].value; // 그룹 Y의 노드 수를 Updata 해준 후 Graph[max].group = Y; //그룹을 V-> Y로 설정 for(int j=0; j< N; j++){ Graph[N].link[j] |= Graph[max].link[j]; //기존의 감시노드와 새로 연결한 노드를 결합 } modify_Graph(); // V 그룹의 그래프의 링크와 링크수를 다시 설정 } } void NetWork::modify_Graph(){ for(int i=0; i<N; i++){ if(Graph[i].group == V){ //변경할 그래프는 그룹 V for(int j=0; j<N; j++){ if((Graph[i].link[j]&Graph[N].link[j])==1){ // 변경할 그래프는 Y그래프와 중첩되야함 Graph[i].link[j] = 0; /링크제거 Graph[i].value--; //링크수를 제거한다. } } } } } int NetWork::get_MaxGraph(){ int max = 0; int maxNum = 0; //처음의 감시노드는 싱크노드 V1로 설정 if(Graph[N].value ==0) return 0; for(int i=0; i<N; i++){ if(Graph[N].link[i]==1){ //Y그래프와 연결되어야 하고 if(Graph[i].value > max && Graph[i].group == V){ // 그룹은 V여야 하며 가장 큰 링크수를 가져야 한다. max = Graph[i].value; maxNum = i; } } } return maxNum; //노드번호 반환 } void NetWork::print(){ //출력함수 for(int i=0; i<N; i++){ //감시노드 집합출력 if(K_Array[i] == 1) cout<< i+1<<" "; } cout<<endl; for(int i=0; i<N; i++){ //Y그래프 출력 if(Graph[N].link[i]==1) cout<< i+1 <<" "; } cout<<endl; } int main(){ fstream fin; fin.open("input.txt"); if(!fin){ cout << "Error opening file" << endl; return 0; } int D; // data 개수 fin >> D; for(int x=0; x < D; x++){ int K; // K의 개수 int N; // Node의 개수 fin >> K; fin >> N; Nptr Graph = new Node[N+1]; //값 입력받고 그래프생성 for(int y=0; y < N+1; y++){ int* Link = new int[N]; Graph[y].link = Link; Graph[y].group = V; // V그룹; Graph[y].value = 0; // 초기 링크수는 0 for(int z=0; z < N && y < N; z++){ fin >> Link[z]; if(Link[z]==1) Graph[y].value++; //링크수 초기화 } } NetWork Net(K+1, N, Graph); Net.make_Graph(); Net.print(); //동적할당해제 for(int y=0; y < N+1; y++){ int* Link = Graph[y].link; delete Link; } delete Graph; } return 0; }

보고서 파일

무선 센서 네트워크에서 감시 노드들의 집합 구하기 _by_AmericanoJH.pdf