알고리즘 과제 #2 (인접한 노드 그래프 생성)

문제 : 센서 네트워크 생성

무선 센서 네트워크는 물리적이나 환경적인 상태 즉 온도, 소리, 진동, 압력, 움직임, 또는 오염 정도를 관찰하기위해 공간적으로 분포되어 있는 독립적인 기능을 수행하는 센서들로 이루어져 있다. 무선 센서 네트워크는 그래프 G = (V, E)로 표현할 수 있는 데, 여기서 V는 센서 노드들의 집합이고 E는 통신 링크들의 집합이다. 두 개의 센서 노드는 전송 범위 안에 있으면 서로 교신을 할 수 있는데 이 경우에 두 노드를 간선으로 연결한다. 

 m x m 정방형 필드에 n개의 센서 노드를 임의로 배치하고, 두 센서 노드의 거리가 t보다 작거나 같으면 간선으로 연결된 그래프의 인접행렬을 출력하는 프로그램을 작성하라. 

입력 형식

입력 파일의 이름은 input.txt이다. 첫째 줄에는 필드의 크기 m, 둘째 줄에는 노드의 개수 n, 셋째 줄에는 교신 범위 t가 주어진다.

출력 형식

출력 파일의 이름은 graph.txt이다. 첫째 줄에는 노드의 개수 n, 그 다음 줄부터 n개의 줄에 인접 행렬을 출력한다.

입력 예

100         // m     6           // n   40          // t

출력 예

6   0 1 1 0 0 0   1 0 0 1 1 0    1 0 0 0 0 1    0 1 0 0 1 0    0 1 0 1 0 0    0 0 1 0 0 0

소스 코드

#include<fstream> #include<iostream> #include "time.h" #include"stdlib.h" using namespace std; /* 프로그램 작성자 : americano@korea.ac.kr 개발 날짜 : 2012-3-25 */ typedef struct GraphNode{int x, y;}node; typedef node* Nptr; class Graph{ public: Graph(){ //m = field's size // n = node's size // t = communication range ifstream fin; ofstream fout; fin.open("input.txt"); fout.open("graph.txt"); fin>>m>>n>>t; srand((unsigned)time(NULL)); Sensor = new node[n]; for(int i=0; i<n; i++){ Sensor[i].x = rand() % m; Sensor[i].y = rand() % m; } fout<<n<<endl; //print node's size for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(i==j) fout<<"0 "; else if((Sensor[i].x-Sensor[j].x)*(Sensor[i].x-Sensor[j].x)+(Sensor[i].y-Sensor[j].y)*(Sensor[i].y-Sensor[j].y) <= t*t) fout<<"1 "; else fout<<"0 "; } fout<<endl; } fin.close(); fout.close(); } ~Graph(){delete [] Sensor;} private: Nptr Sensor; int m,n,t; }; int main(){ Graph g; return 0;}