BFS 를 사용해 미로의 최단 경로 출력하기

미로 찾기 문제는 대표적인 스택과 큐의 응용 예제입니다. 

 

Ex. 7*15 미로

0 1 0 0 0 1 1 0 0 0 1 1 1 1 1

1 0 0 0 1 1 0 1 1 1 0 0 1 1 1

0 1 1 0 0 0 0 1 1 1 1 0 0 1 1

1 1 0 1 1 1 1 0 1 1 0 1 1 0 0

1 1 0 1 0 0 1 0 1 1 1 1 1 1 1

0 0 1 1 0 1 1 1 0 1 0 0 1 0 1

0 0 1 1 0 1 1 1 0 1 0 0 1 0 1

 

1은 벽이고, 0은 이동할 수 있는 길입니다. 이 문제의 경우 동서남북만 이동할 수 있는 것이 아니라 아래 처럼 8방향으로 모두 이동이 가능합니다.

실제 미로는 테두리로 1을 삥 두를 것이기 때문에 미로를 저장하는 배열은 maze[7][15] 이 아닌 maze[7+2][15+2]의 크기로 선언됩니다. 미로의 크기가 m*p 라면 미로를 저장하는 배열은 maze[m+2][p+2] 가 됩니다.

 

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1

1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1

1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1

1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1

1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1

1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1

1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

 

실제로는 위 같은 형태로 저장 되는 것이죠.

 

미로의 경로를 찾는 문제는 대표적으로 스택을 사용해 구현할 수 있습니다. 이동할 수 있는지 없는지 (0인지 1인지 + 방문을 했는지 안했는지 체크하는 2차원 배열을 통해 방문한 곳은 다시 방문 X) 를 체크하고, 이동한 좌표들은 모조리 스택에 넣은 이후 만약 더 이상 이동할 수 없으면 Pop을 통해 다시 갈림길로 돌아가는 것을 반복하는 아이디어를 사용합니다.

 

일종의 DFS와 굉장히 비슷한데요, 이를 통해 구한 경로는 "최단 경로"는 아닙니다. 우선 코드를 한 번 보겠습니다.

void Path(const int m, const int p) {
	mark[1][1] = 1;
	stack<Items> stack;
	Items temp(1, 1, E);
	stack.push(temp);

	while (!stack.empty()) {
		temp = stack.top(); stack.pop();
		int i = temp.x; int j = temp.y; int d = temp.dir;
		while (d < 8)
		{
			int g = i + Move[d].a;
			int h = j + Move[d].b;

			if ((g == m) && (h == p)) { // 출구를 찾은 경우
				cout << "\nPath 의 출력 결과\n" << endl;
				cout << stack;
				temp.x = i; temp.y = j; 
				cout << " -> " << temp;
				temp.x = m; temp.y = p; 
				cout << " -> " << temp << endl;
				return;
			}

			if ((!maze[g][h]) && (!mark[g][h])) {
				mark[g][h] = 1; // 방문 표시
				temp.x = i; temp.y = j; temp.dir = d + 1;
				// 현재의 위치와 다음 시도 방향 지정
				stack.push(temp);
				i = g; j = h; d = N; // N 방향부터 (시계방향으로) 시도
			}
			else d++;
		}
	}

	cout << "No path in maze." << endl;
}

이 코드가 돌아가려면 연산자 오버로딩 등의 나머지 코드들이 필요하긴 한데 전체 코드는 맨 아래에서 보고 지금은 핵심 아이디어만 확인해보겠습니다. 위에서 말했듯 처음 시작점을 스택에 넣고 while문을 통해 스택이 비어있을 때까지, 즉 출구를 찾지 못할 때까지 무한 반복합니다. 출구를 찾았다면 스택에는 그간 이동한 좌표들이 모두 담겨있을 것이고, 이를 꺼내어 출력해주면 됩니다.

 

while 안에서는 먼저 스택에 최상단의 좌표를 꺼내고, 그 좌표와 방향에 대해 저장한 이후, 8에 대해, 즉 8개의 방향에 대해 모두 체크를 해보는 겁니다. 만약 중간에 출구를 찾는다면 return을 하는 것이고 이동한 좌표에서 또 다시 이동할 수 있는 경로가 있다면 push를 하는 것이죠. DFS와 원리가 동일합니다.

 

그러나 미로의 "최단" 경로를 출력하는 것은 또 아예 다른 문제입니다. 우선 출력 결과를 보면서 설명해보겠습니다.

Path는 스택을 이용해 출구를 찾는 함수, ShortestPath는 BFS를 사용해 최단 경로를 출력하는 함수입니다. 위 출력은 12*15 미로에 대해 수행한 결과로 스택을 사용한 경로에서는 30번의 이동 끝에 출구를 찾는 반면 ShortestPath 에서는 25번만에 출구를 찾는 것을 확인할 수 있습니다.

 

사실 DFS로도 최단 경로를 찾을 수는 있습니다. 해결 방법은 DFS로 갈 수 있는 모든 경로를 체크하여 길이가 가장 짧은 것을 탐색하면 되기 때문입니다. 그러나 이 방법은 Brute force나 다름 없을 정도로 비효율적인 알고리즘 입니다.

 

[알고리즘] BFS (너비 우선 탐색)

BFS를 사용해 각 단계마다 뻗어나갈 수 있는 좌표를 모두 체크하면서 추후 출력을 위해서 "이전 단계에 대한 정보를 담고 있는 임시 미로"를 만들고 거기에 어디에서부터 이 좌표로 이동했는지에 대한 정보를 저장해 출력단에서 임시 미로를 출력하는 방식으로 최단 경로 출력을 하였습니다.

 

void ShortestPath(const int m, const int p) {
	queue<Items> q;

	Items prev[MAXSIZE + 1][MAXSIZE + 1];

	Items initial(1, 1, E);	// 시작점

	// 시작점 큐에 넣고 방문 표시
	q.push(initial);
	visited[1][1] = true;

	while (!q.empty()) {
		Items cur = q.front();
		q.pop();

		if (cur.x == m && cur.y == p) { // 출구를 찾은 경우
			vector<Items> path; // 경로를 저장하기 위한 스택
			// stack 은 연산자 오버로딩을 뒤집어 출력하게 만들어서 vector 사용
			
			/*
			// prev 정보 체크
			for (int i = 1; i <= m; i++) {
				for (int j = 1; j <= p; j++)
					cout << prev[i][j] << " ";
				cout << endl;
			}
			*/

			// 경로를 출력
			cout << "\nShortestPath 의 출력 결과\n" << endl;
			
			// 입구를 찾을 때까지 
			while (!((cur.x == 1) && (cur.y == 1))) {
				path.push_back(cur);
				cur = prev[cur.x][cur.y];
			}

			cout << " -> " << initial;
			cout << path;
			
			return;
		}

		int d = 0;
		while (d < 8) {
			int g = cur.x + Move[d].a;
			int h = cur.y + Move[d].b;

			// 갈 수 있는 위치라면 방문 표시 후 Push
			if ((!maze[g][h]) && (!visited[g][h])) {
				visited[g][h] = true; // 방문 표시
				prev[g][h] = cur;	  // prev 정점 기록

				Items temp(g, h);
				q.push(temp);
			}
			else {		// 해당 방향으로 이동할 수 없는 경우
				d++;	// 방향 전환
			}
		}
	}

	cout << "No path in maze." << endl;
}

 

제가 짠 코드라 비효율적인 부분이 많을 수 있습니다. 전체 코드만 올리고 마무리하도록 하겠습니다.

 

// maze.cpp
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

const int MAXSIZE = 100;
bool maze[MAXSIZE + 2][MAXSIZE + 2];
bool mark[MAXSIZE][MAXSIZE] ={ 0 };
bool visited[MAXSIZE + 1][MAXSIZE + 1] = { false };


enum directions { N, NE, E, SE, S, SW, W, NW};

struct offsets {
	int a, b;
} Move[8] = {
			{-1, 0}, {-1, 1},
			{0, 1}, {1, 1},
			{1, 0}, {1, -1},
			{0, -1}, {-1, -1},
};

struct Items {
	Items(int xx = 0, int yy = 0, int dd = 0) : x(xx), y(yy), dir(dd) {}
	int x, y, dir;
};

template <class T>
ostream& operator<<(ostream& os, stack<T>& s) {
	stack<T> temp;
	while(!s.empty()) {
		temp.push(s.top());
		s.pop();
	}

	while(!temp.empty()) {
		os << " -> " << temp.top();
		temp.pop();
	}
	
	return os;
}

template <class T>
ostream& operator<<(ostream& os, vector<T>& s) {
	while (!s.empty()) {
		os << " -> " << s.back();
		s.pop_back();
	}

	return os;
}

ostream& operator<<(ostream& os, Items& item)
{
	static int count = 0;
	os << "(" << item.x << "," << item.y << ")";
	count++;

	if (count % 5 == 0) cout << endl;
	return os;
}

void Path(const int m, const int p) {
	mark[1][1] = 1;
	stack<Items> stack;
	Items temp(1, 1, E);
	stack.push(temp);

	while (!stack.empty()) {
		temp = stack.top(); stack.pop();
		int i = temp.x; int j = temp.y; int d = temp.dir;
		while (d < 8)
		{
			int g = i + Move[d].a;
			int h = j + Move[d].b;

			if ((g == m) && (h == p)) { // 출구를 찾은 경우
				cout << "\nPath 의 출력 결과\n" << endl;
				cout << stack;
				temp.x = i; temp.y = j; 
				cout << " -> " << temp;
				temp.x = m; temp.y = p; 
				cout << " -> " << temp << endl;
				return;
			}

			if ((!maze[g][h]) && (!mark[g][h])) {
				mark[g][h] = 1; // 방문 표시
				temp.x = i; temp.y = j; temp.dir = d + 1;
				// 현재의 위치와 다음 시도 방향 지정
				stack.push(temp);
				i = g; j = h; d = N; // N 방향부터 (시계방향으로) 시도
			}
			else d++;
		}
	}

	cout << "No path in maze." << endl;
}


void ShortestPath(const int m, const int p) {
	queue<Items> q;

	Items prev[MAXSIZE + 1][MAXSIZE + 1];

	Items initial(1, 1, E);	// 시작점

	// 시작점 큐에 넣고 방문 표시
	q.push(initial);
	visited[1][1] = true;

	while (!q.empty()) {
		Items cur = q.front();
		q.pop();

		if (cur.x == m && cur.y == p) { // 출구를 찾은 경우
			vector<Items> path; // 경로를 저장하기 위한 스택
			// stack 은 연산자 오버로딩을 뒤집어 출력하게 만들어서 vector 사용
			
			/*
			// prev 정보 체크
			for (int i = 1; i <= m; i++) {
				for (int j = 1; j <= p; j++)
					cout << prev[i][j] << " ";
				cout << endl;
			}
			*/

			// 경로를 출력
			cout << "\nShortestPath 의 출력 결과\n" << endl;
			
			// 입구를 찾을 때까지 
			while (!((cur.x == 1) && (cur.y == 1))) {
				path.push_back(cur);
				cur = prev[cur.x][cur.y];
			}

			cout << " -> " << initial;
			cout << path;
			
			return;
		}

		int d = 0;
		while (d < 8) {
			int g = cur.x + Move[d].a;
			int h = cur.y + Move[d].b;

			// 갈 수 있는 위치라면 방문 표시 후 Push
			if ((!maze[g][h]) && (!visited[g][h])) {
				visited[g][h] = true; // 방문 표시
				prev[g][h] = cur;	  // prev 정점 기록

				Items temp(g, h);
				q.push(temp);
			}
			else {		// 해당 방향으로 이동할 수 없는 경우
				d++;	// 방향 전환
			}
		}
	}

	cout << "No path in maze." << endl;
}


void getdata(istream& is, int& m, int& p) {
	is >> m >> p;
	// 미로 위아래 테두리
	for (int i = 0; i < m + 2; i++) { maze[i][0] = 1; maze[i][p + 1] = 1; }

	// 미로 좌우 테두리
	for (int j = 1; j <= p; j++) { maze[0][j] = 1; maze[m + 1][j] = 1; }

	// maze.in 파일을 읽어 나머지 미로 채우기
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= p; j++)
			is >> maze[i][j];

	// 미로 출력 체크
	/*
	for (int i = 0; i <=m+1 ; i++) {
		for (int j = 0; j <= p+1; j++)
		{
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}
	*/
}

// main.cpp
#include <iostream>
#include <fstream>
#include "stdlib.h"
using namespace std;

void getdata(istream&, int&, int&);
void Path(int, int);
void ShortestPath(int, int);


int main(int argc, char* argv[])
{
	int m, p; // m*p maze
	if (argc == 1)
		cerr << "Usage: " << argv[0] << "maze_data_file" << endl;
	else {
		ifstream is(argv[1]);
		if (!is) { cerr << argv[1] << "does not exist\n"; exit(1); }
		cout << "For maze datafile (" << argv[1] << ")\n";
		getdata(is, m, p);
		is.close();
		Path(m, p);
		ShortestPath(m, p);
	}
}

 

 

Reference : Ellis, Horowitz. C++ 자료구조론(2판). 대한민국: 인피니티북스, 2007.