C++로 BFS, DFS 구현

< BFS >

 

#include <iostream>
#include <queue>

// x가 행, y가 열
#define X first
#define Y second

int board[502][502] =
{ {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} };
bool visited[502][502];

int n = 7, m = 10;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	//std::ios::sync_with_stdio(0);
	//std::cin.tie(0);

	std::queue<std::pair<int, int>> queue;
	visited[0][0] = 1;
	queue.push({ 0,0 });

	while (!queue.empty()) {
		std::pair<int, int> cur = queue.front();
		queue.pop();
		std::cout << '(' << cur.X << ", " << cur.Y << ") -> ";

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (visited[nx][ny] || board[nx][ny] != 1)
				continue;

			visited[nx][ny] = 1;
			queue.push({ nx, ny });
		}
	}
}

 

 

< DFS >

 

#include <iostream>
#include <stack>

// x가 행, y가 열
#define X first
#define Y second

int board[502][502] =
{ {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} };
bool visited[502][502];

int n = 7, m = 10;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	//std::ios::sync_with_stdio(0);
	//std::cin.tie(0);

	std::stack<std::pair<int, int>> stack;
	visited[0][0] = 1;
	stack.push({ 0,0 });

	while (!stack.empty()) {
		std::pair<int, int> cur = stack.top();
		stack.pop();
		std::cout << '(' << cur.X << ", " << cur.Y << ") -> ";
		
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (visited[nx][ny] || board[nx][ny] != 1)
				continue;

			visited[nx][ny] = 1;
			stack.push({ nx, ny });
		}
	}
}

 

---

< 참고자료 >

 

https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

https://blog.encrypted.gg/942

[실전 알고리즘] 0x0A강 - DFS