간선에 가중치를 부여하고 Prim algorithm 으로 미로 만들기

Study

간선에 가중치를 부여하고 Prim algorithm 으로 미로 만들기

bslime 2009. 6. 3. 18:16

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

#define FALSE 0
#define TRUE 1

typedef struct _node {
	int vertex;
	int weight;
	struct _node *next;
} node;

typedef struct _F {
	int front;
	int rear;
	int weight;
	struct _F *next;
} F;

typedef struct _Y {
	int vertex;
	struct _Y *next;
} Y;

int count = 0;

FILE *maze = '\0';
node **head;
node *mesh;
F *f;
Y *y;
struct _F line;

int NEW(int x);
int MESH(int x, int y);
int PRIM(int x);
int MAKEY(int x);
int FINDLINE();
int MAKEF(int x, int y);
int SCAN(int x);

int main() {
	int a, b, i;

F *output;

maze = fopen("maze.config", "w+");

scanf("%d", &a);
	b = a * a;
	
	head = (node **)malloc(sizeof(node) * b);
	NEW(b);
	MESH(b, a);
	PRIM(b);

output = f;	
	
	while(output != NULL) {
		printf("%d %d\n", output->front, output->rear);
		fprintf(maze, "%d %d\n", output->front, output->rear);
		output = output->next;
	}

fclose(maze);

return 0;
}

int NEW(int x) {
	int i;
	for(i = 1; i <= x; i++) 
		head[i] = (node *)NULL;
	return 0;
}

int MESH(int x, int y) {
	int u, v, w;

srand((unsigned)time(NULL));
	
	for(u = 1; u <= x - 1 ; u++) {
		v = u + 1;
		if(u % y != 0) {
			w = rand() % 10 + 1;
			
			mesh = (node *)malloc(sizeof(node));
			mesh->vertex = u;
			mesh->weight = w;
			mesh->next = head[v];
			head[v] = mesh;
			
			mesh = (node *)malloc(sizeof(node));
			mesh->vertex = v;
			mesh->weight = w;
			mesh->next = head[u];
			head[u] = mesh;			
		}

v = u + y;
		if(u < x - y + 1) {
			w = rand() % 10 + 1;

mesh = (node *)malloc(sizeof(node));
			mesh->vertex = u;
			mesh->weight = w;
			mesh->next = head[v];
			head[v] = mesh;
					
			mesh = (node *)malloc(sizeof(node));
			mesh->vertex = v;
			mesh->weight = w;
			mesh->next = head[u];
			head[u] = mesh;
		}
	}
	return 0;
}

int PRIM(int x) {
	int i;
	
	f = (F *)NULL;
	y = (Y *)NULL;
	
	MAKEY(1);
	
	for(i = 1; i <= x - 1; i++)
		FINDLINE();

return 0;
}

int MAKEY(int x) {
	Y *list;

list = (Y *)malloc(sizeof(Y));
	list->vertex = x;
	list->next = y;
	y = list;
	
	return 0;
}

int FINDLINE() {
	int min;
	
	node *find;
	Y *list;
		
	min = 11;

for(list = y; list != NULL; list = list->next) {
		for(find = head[list->vertex]; find != NULL; find = find->next) {
			if(SCAN(find->vertex) && (min > find->weight)) {
				min = find->weight;
			}
		}
	}
	
	for(list = y; list != NULL; list = list->next) {
		for(find = head[list->vertex]; find != NULL; find = find->next) {			
			if(SCAN(find->vertex) && (min == find->weight)) {
				line.front = list->vertex;
				line.rear = find->vertex;
				line.weight = find->weight;
			}
		}
	}
	
	MAKEY(line.rear);
	
	MAKEF(line.front, line.rear);
	
	return 0;
}

int MAKEF(int x, int y) {
	F *makef;

makef = (F *)malloc(sizeof(F));
	makef->front = x;
	makef->rear = y;
	makef->next = f;
	f = makef;
		
	return 0;
}

int SCAN(int x) {
	Y *list;

list = y;
	while(list != NULL) {
		if(list->vertex == x) {
			return FALSE;
		}
		list = list->next;
	}	
	return TRUE;
}

사실 난 별로 손댄곳이 없다, -_-