덱(Deque)응용 미로 탐색 프로그램

미로에서 출구를 찾기 위한 다양한 탐색 방법을 사용할 수 있다.

이것은 그래프 탐색 문제와 유사하며 다양한 방법들이 있다. 

가장 간단한 탐색 방법은 시행착오를 이용하는 것으로 하나의 경로를 선택하여 시도해 보고 막히면 다시 다른 경로를 시도하는 것이다.

이때 현재의 경로가 막혔을 때 다시 선택할 수 있는 다른 경로들을 어딘가에 저장해야 한다. 저장된 경로를 모두 선택할 수 있는 방법이라면

경로를 어디에 저장하든지 출구를 찾을 수 있다. 전통적으로 그래프 탐색에서는 대표적인 두 가지 방법을 제공한다.

깊이 우선 탐색(DFS, Depth First Search) 전략: 가장 최근에 저장한 경로를 순서대로 선택하여 시도하는 방법. 스택을 이용해서 구현

너비 우선 탐색(BFS, Breadth First Search) 전략: 가장 먼저 저장된 경로를 선택하여 시도하는 방법. 큐를 이용해서 구현

깊이 우선 탐색을 더 구체적으로 살펴보면 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 기억했다가 막다른 길을 만나면 가장 최근에 저장

한 아직 가보지 않은 방으로부터 새로운 경로를 시작한다. 한번 가본 방은 다시 가면 안되므로 표시를 해서 다시 가지 않도록 해야 한다.

현재위치가 출구가 아니면 이동이 가능한 이웃(상하좌우) 칸의 위치를 스택에 저장한다. 다음으로 스택에서 하나의 위치를 꺼내 현재의 위치

로 설정하고, 같은 작업을 반복한다. 반복은 현재의 위치가 출구와 같거나 더 이상 갈 수 있는 위치가 없을 때까지 계속된다. 

너비 우선 탐색은 경로 저장에 큐가 사용되는 것을 제외하고는 모든 것이 동일하다.

미로 탐색 알고리즘

모든 위치는 (행, 열)로 표시한다. 입구 위치를 스택(또는 큐)에 넣어주면 탐색이 시작된다. 현재 스택에는 입구 위치만 들어 있다. 스택이 공백

상태가 아닌 동안 하나의 위치를 꺼내 탐색하는 과정을 반복한다. 만약 스택이 공백상태이면 이 미로에는 출구가 없다. 

만약 현재 위치 (r,c)가 출구이면 탐색은 성공적으로 끝난다. 

#include<stdio.h>
#include<stdlib.h>
#define MAX_QUEUE_SIZE 100

typedef struct {
	int x;
	int y;
}Location2D;
typedef Location2D Element;

Element data[MAX_QUEUE_SIZE];

int front, rear;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_queue() { front = rear = 0; ; }
int is_empty() { return front == rear; }
int is_full() { return front == (rear + 1) % MAX_QUEUE_SIZE; }
int size() { return (rear - front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; }

void enqueue(Element val)
{
	if (is_full())
		error("큐 포화 에러");
	rear = (rear + 1) % MAX_QUEUE_SIZE;
	data[rear] = val;
}

Element dequeue()
{
	if (is_empty())
		error("큐 공백 에러");
	front = (front + 1) % MAX_QUEUE_SIZE;
	return data[front];
}

Element peek()
{
	if (is_empty())
		error("큐 공백 에러");
	return data[(front + 1) % MAX_QUEUE_SIZE];
}

void init_deque() { init_queue(); }
void add_rear(Element val) { enqueue(val); }
Element delete_front() { return dequeue(); }
Element get_front() { return peek(); }

void add_front(Element val)
{
	if (is_full())
		error("덱 포화 에러");
	data[front] = val;
	front = (front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

Element delete_rear()
{
	int prev = rear;
	if (is_empty())
		error("덱 공백 에러");
	rear = (rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return data[prev];
}

Element get_rear()
{
	if (is_empty())
		error("덱 공백 에러");
	return data[rear];
}

#define MAZE_SIZE 6

char map[MAZE_SIZE][MAZE_SIZE] = {
	{'1', '1', '1', '1', '1', '1'},
	{'e', '0', '1', '0', '0', '1'},
	{'1', '0', '0', '0', '1', '1'},
	{'1', '0', '1', '0', '1', '1'},
	{'1', '0', '1', '0', '0', 'x'},
	{'1', '1', '1', '1', '1', '1'}
};

Location2D getLocation2D(int x, int y) {
	Location2D p;
	p.x = x;
	p.y = y;
	return p;
}

int is_valid(int x, int y) {
	if (x < 0 || y < 0 || x >= MAZE_SIZE || y >= MAZE_SIZE) return 0;
	else return map[y][x] == '0' || map[y][x] == 'x';
}

int DFS()
{
	int x, y;
	Location2D here;
	
	init_deque();
	add_rear(getLocation2D(0, 1));
	printf("DFS: ");
	while (is_empty() == 0) {
		here = delete_rear();
		printf("(%2d,%2d)", here.x, here.y);
		x = here.x;
		y = here.y;
		if (map[y][x] == 'x') return 1;
		else {
			map[y][x] = '.';
			if (is_valid(x-1, y)) add_rear(getLocation2D(x-1, y));
			if (is_valid(x+1, y)) add_rear(getLocation2D(x+1, y));
			if (is_valid(x, y-1)) add_rear(getLocation2D(x, y-1));
			if (is_valid(x, y+1)) add_rear(getLocation2D(x, y+1));


		}
	}
	return 0;
}

int BFS()
{
	int x, y;
	Location2D here;

	init_deque();
	add_rear(getLocation2D(0, 1));
	printf("BFS: ");
	while (is_empty() == 0) {
		here = delete_front();
		printf("(%2d,%2d)", here.x, here.y);
		x = here.x;
		y = here.y;
		if (map[y][x] == 'x') return 1;
		else {
			map[y][x] = '.';
			if (is_valid(x - 1, y)) add_rear(getLocation2D(x - 1, y));
			if (is_valid(x + 1, y)) add_rear(getLocation2D(x + 1, y));
			if (is_valid(x, y - 1)) add_rear(getLocation2D(x, y - 1));
			if (is_valid(x, y + 1)) add_rear(getLocation2D(x, y + 1));
		}
	}
	return 0;
}

void main()
{
	//printf("->%s\n", DFS() ? "성공" : "실패");
	printf("->%s\n", BFS() ? "성공" : "실패");
}