<모든 코드는 C++를 기반으로 작성되었습니다.>

Chapter 5 :: 탐색 알고리즘 DFS / BFS

예제 1. 음료수 얼려 먹기

• DFS의 단골문제중 하나인 부분 그래프 개수 찾기 문제다.
• 임의의 좌표에서부터 시작해서 인접한 칸의 값이 0일 때 진행한다.
• DFS가 1회 종료되서 나올 때마다 카운트 해준다. 왜냐하면 DFS가 한 번 종료됐다는 것은 이어진 인접한 노드들로 이뤄진 한 부분 그래프를 하나 찾아낸 것이기 때문이다.

#include <iostream>
using namespace std;

static int N, M;
static bool ice[1000][1000];
static constexpr int moving[4][2] {
	{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

inline bool isSafe(int y, int x) {
	return ((0 <= y && y < N) && (0 <= x && x < M));
}

void dfs(int y, int x) {
	ice[y][x] = true; 
	for (int i = 0; i < 4; ++i) {
		int newY = y + moving[i][0], newX = x + moving[i][1];
		if (isSafe(newY, newX) && !ice[newY][newX]) dfs(newY, newX);
	}
}

int solve() {
	int ret = 0;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j) // 모든 좌표에 대해 DFS를 돌린다.
			if (!ice[i][j]) { dfs(i, j); ret++;}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			int input = 0; cin >> input;
			ice[i][j] = (input == 0) ? false : true;
		}
	}
	cout << solve() << '\n';
}

• DFS를 구현하는 방법은 여러가지겠지만, 여기서는 각 칸이 0, 1값만 가진다는 것을 고려해서 맵을 bool타입으로 구현했고, isVisited[]배열을 사용하지 않았다. 왜냐하면 탐색된 칸을 1 또는 true로 바꿔주면 되기 때문이다.

예제 2. 미로탈출

• 출발 지점부터 종료 지점까지 최단 거리로 이동해서 미로를 탈출해야한다.
• '다익스트라', '벨만포드', '플루이드'같은 최단거리 알고리즘을 사용해도 되지만, 여기서는 BFS를 이용해서 풀어보도록 한다.
• BFS를 사용한 이유는, DFS와는 달리 BFS는 언제나 최적해를 보장하기 때문이다.

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

static int N, M;
static bool maze[200][200];
static constexpr int moving[4][2] {
	{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

inline bool isSafe(int y, int x) {
	return ((0 <= y && y < N) && (0 <= x && x < M));
}

int solve() {
	queue<tuple<int, int, int>> q;
	q.push(make_tuple(0, 0, 1));

	while (!q.empty()) {
		int y, x, cost; tie(y, x, cost) = q.front();
		q.pop();
		maze[y][x] = false;

		if (y == N - 1 && x == M - 1) return cost;

		for (int i = 0; i < 4; ++i) {
			int newY = y + moving[i][0], newX = x + moving[i][1];
			if (isSafe(newY, newX) && maze[newY][newX])
				q.push(make_tuple(newY, newX, cost + 1));
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j) {
			int input = 0; cin >> input;
			maze[i][j] = (input == 0) ? false : true;
		}
	cout << solve() << '\n';
}

• 사실 이 문제는 tuple 자료구조를 쓰지 않고 외부에 변수를 하나 더 만들어서 시작지점으로부터 (y, x)까지 이르는 최단거리를 기록하는 방식으로 푸는게 맞다.
• 근데 메모리 조금 더 아끼고 싶어서 욕심을 부렸다. ㅎㅎ
• 이 문제는 항상 출구를 찾을 수 있는 경우만 입력으로 들어오므로 solve()함수는 조건에 해당할 때만 return 되도록 만들어도 된다. while()문이 종료되는 경우는 없다.