DFS, BFS Algorithm 을 이용한 미로 길 찾기

Study 2009. 6. 3. 18:19

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

#define FALSE 0
#define TRUE 1

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

typedef struct _Queue {
	int vertex;
	struct _Queue *next;
} Queue;

FILE *maze = '\0';
node **head;
node *list;
Queue *queue;
Queue *new;
Queue *old;

int *rank;
int *parent;
int *flag;
int mark;
int *print;
int pcount = 0;

int MAKESET(int x);
int FIND(int x);
int UNION(int x, int y);
int NEW(int x);
int LIST(int x);
int DFS(int x);
int DFS_VISIT(int v, int x);
int BFS(int x);
int BFS_VISIT(int x);
int INIT_QUEUE(void);
int ENQUEUE(int x);
int QUEUE_EMPTY();
int DELQUEUE();
int PATH(int x);

int main() {
	int a, b, i, p, q, pp, qp;
	double ms1, ms2;
	struct timeval *st, *et;
	maze = fopen("maze.config", "w+");
	
	a = 1000;
	b = 1000000;
	
	parent = (int *)malloc(sizeof(int) *(b + 1));
	rank = (int *)malloc(sizeof(int) *(b + 1));
	for(i = 1; i <= b; i++)
		MAKESET(i);
	i = 0;	
	while(i < b - 1) {
		p = (rand() % b) + 1;
		q = (rand() % 4);
		if(q == 0)
			q = p - 1;
		else if(q == 1)
			q = p + 1;
		else if(q == 2)
			q = p - a;
		else if(q == 3)
			q = p + a;
		if(p % a == 0 && q == p + 1)
			continue;
		if(q < 0 || q == p || q % a == 0)
			continue;
		if(p > b - a && q > b || q > b - a && p > b)
			continue;
		
		if(q > 0 && q < b) {
			if((pp = FIND(p)) != (qp = FIND(q))) {
				if(q >= p) {
					fprintf(maze, "%d %d\n", p, q);
					UNION(pp, qp);
				}
				else {
					fprintf(maze, "%d %d\n", q, p);
					UNION(qp, pp);
				}
			i++;
			}
		}
	}
	
	fseek(maze, 0, SEEK_SET);
	head = (node **)malloc(sizeof(node) * b);
	flag = (int *)malloc(sizeof(int) *(b + 1));
	NEW(b);
	LIST(b);
	fclose(maze);
	
	st = (struct timeval *)malloc(sizeof(struct timeval));
	et = (struct timeval *)malloc(sizeof(struct timeval));
	
	gettimeofday(st, 0);
	DFS(b);
	gettimeofday(et, 0);
	ms1 = (et->tv_sec - st->tv_sec) * 1000000 + (et->tv_usec - st->tv_usec);
	
	gettimeofday(st, 0);
	BFS(b);
	gettimeofday(et, 0);
	ms2 = (et->tv_sec - st->tv_sec) * 1000000 + (et->tv_usec - st->tv_usec);

printf("shortest path\n");
	for(i = 0; i < pcount; i++)
		printf("%d ", print[i]);
	printf("\n");
	printf("\nrunning time\n");
	printf("dfs_ms = %f(s)\nbfs_ms = %f(s)\n", ms1 / 100000, ms2 / 100000);

return 0;
}

int MAKESET(int x) {
	parent[x] = x;
	rank[x] = 0;
	return 0;
}

int FIND(int x) {
	if(x != parent[x])
		parent[x] = FIND(parent[x]);
	return parent[x];
}

int UNION(int x, int y) {
	int u, v;
	u = FIND(x);
	v = FIND(y);
	if(rank[u] > rank [v])
		parent[v] = u;
	else {
		parent[u] = v;
		if(rank[u] == rank[v])
			rank[v]++;
	}
	return 0;
}

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

int LIST(int x) {
	int i, u, v;
	char Buff[100];

for(i = 1; i <= x - 1 ; i++) {
		if(fgets(Buff, 256, maze) == "\n")
			break;
		sscanf(Buff, "%d %d\n", &u, &v);

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

int DFS(int x) {
	int v;
	mark = 0;

for(v = 1; v <= x; v++)
		flag[v] = 0;

for(v = 1; v <= x; v++) {
		if(flag[v] == 0) {
			DFS_VISIT(v, x);
			if(v == 1)
				PATH(v);
		}
	}
	return 0;
}

int DFS_VISIT(int v, int x) {	
	node *list;
	mark++;
	flag[v] = mark;
	list = head[v];

if(v == x)
		return TRUE;

while(list != NULL) {
		if(flag[list->vertex] == 0) {
			if((DFS_VISIT(list->vertex, x) != FALSE)) {
				PATH(list->vertex);
				return TRUE;
			}	
		}
		list = list->next;
	}

return 0;
}

int BFS(int x) {
	int v;
	mark = 0;
	INIT_QUEUE();	
	for(v = 1; v <= x; v++)
		flag[v] = 0;

for(v = 1; v <= x; v++) {
		if(flag[v] == 0)
			BFS_VISIT(v);
	}
	return 0;
}

int BFS_VISIT(int x) {
	node *list;
	int u;
	ENQUEUE(x);
	flag[x] = -1;
	while(!QUEUE_EMPTY()) {
		u = DELQUEUE();
		mark++;
		flag[u] = mark;
		for(list = head[u]; list != NULL; list = list->next) {
			if(flag[list->vertex] == 0) {
				ENQUEUE(list->vertex);
				flag[list->vertex] = -1;
			}
		}
	}
	return 0;
}

int INIT_QUEUE() {
	queue = (Queue *)NULL;
	return 0;
}

int ENQUEUE(int x) {
	if(queue == NULL) {
		queue = (Queue *)malloc(sizeof(Queue));
		queue->vertex = x;
		queue->next = NULL;
	}
	else {
		new = (Queue *)malloc(sizeof(Queue));
		new->vertex = x;
		new->next = NULL;
		old = queue;
		while(old->next != NULL)
			old = old->next;
		old->next = new;
	}
	return 0;
}

int QUEUE_EMPTY() {
	if(queue == NULL) {
		return TRUE;
	}

return FALSE;
}

int DELQUEUE() {
	Queue *old = queue;
	int item;
	if(QUEUE_EMPTY())
		return 0;
	else {
		item = old->vertex;
		queue = queue->next;
		free(old);
		return item;
	}
}

int PATH(int x) {
	int i, temp[100000];
	pcount++;

if(pcount == 1)
		print = (int *)malloc(sizeof(int) *pcount + 1);

for(i = 1; i <= pcount; i++)
		temp[i - 1] = print[i - 1];
	
	print = (int *)malloc(sizeof(int) *pcount + 1);

for(i = 1; i <= pcount; i++)
		print[i] = temp[i - 1];
	print[0] = x;
	return 0;
}

사실 이것도 난 별로 손댄게 없다, -_-;;