미로 찾기: 너비 우선 탐색(BFS)의 활용
주어진 M행 N열의 미로에서 특정 시작 지점에서 출구까지의 최단 경로를 찾는 문제는 전형적인 그래프 탐색 문제입니다. 이 미로에는 이동 가능한 칸(1)과 벽(0)이 있으며, 상하좌우로만 이동할 수 있습니다. 우리는 방문했던 칸을 중복하여 지나지 않는 단순 경로를 찾아야 합니다.
그래프 탐색 알고리즘 개요: DFS와 BFS
이러한 유형의 문제에는 주로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지 알고리즘이 사용됩니다. DFS는 경로를 깊이 파고들어 탐색하는 방식이며, 스택 또는 재귀 호출을 통해 구현됩니다. 이는 모든 가능한 경로를 탐색하는 데 유용하지만, 최단 경로를 찾기 위해서는 모든 경로를 탐색하고 그중 가장 짧은 경로를 비교하는 추가적인 로직이 필요하여 효율적이지 않을 수 있습니다.
반면, 너비 우선 탐색(BFS)은 시작점에서 가까운 노드부터 차례대로 탐색하는 방식입니다. 이는 마치 물이 퍼져나가는 것처럼 시작점에서 한 칸씩 모든 방향으로 동시에 탐색 범위를 넓혀나갑니다. 이 특성 덕분에, BFS는 모든 간선의 가중치가 동일한(즉, 비가중치 그래프) 경우 최단 경로를 찾는 데 가장 효율적인 알고리즘입니다. 미로 찾기 문제처럼 한 칸 이동하는 데 드는 비용이 모두 동일하다면, 목표 지점에 가장 먼저 도달하는 경로가 곧 최단 경로가 됩니다.
BFS 구현을 위한 핵심 요소
BFS를 구현하기 위해서는 다음과 같은 요소들이 필요합니다:
- 큐(Queue): 탐색할 다음 노드들을 저장하는 데 사용됩니다. BFS는 큐의 FIFO(First-In, First-Out) 특성을 활용하여 레벨별 탐색을 수행합니다.
- 방문 배열(Visited Array): 각 칸을 방문했는지 여부를 기록하여, 이미 방문한 칸은 다시 탐색하지 않도록 합니다. 이는 무한 루프를 방지하고 탐색 효율성을 높입니다.
- 경로 추적 배열(Predecessor Array): 최단 경로를 역추적하기 위해, 각 칸에 도달하기 직전의 칸(부모 노드)의 좌표를 저장합니다.
C-스타일 BFS 구현 예시
다음은 C 언어 스타일로 미로 찾기 BFS 알고리즘을 구현한 예시입니다. C++ STL(Standard Template Library)을 사용하지 않고 배열로 큐를 직접 구현하여 보여줍니다.
전역 변수 및 초기 설정
#include <stdio.h>
#include <stdbool.h> // for bool type
#define MAX_DIM 105 // 미로의 최대 크기 + 여유 공간
// 미로 지도: 1은 이동 가능, 0은 벽
int maze_grid[MAX_DIM][MAX_DIM];
// 방문 여부 기록
bool visited_status[MAX_DIM][MAX_DIM];
// BFS 탐색을 위한 큐 (좌표 저장)
int coord_queue[MAX_DIM * MAX_DIM][2];
// 이전 좌표를 기록하여 경로 역추적
int parent_coord[MAX_DIM][MAX_DIM][2];
int num_rows, num_cols; // 미로의 행과 열 크기
int start_row, start_col; // 시작 지점
int end_row, end_col; // 도착 지점
// 상, 하, 좌, 우 이동을 위한 델타 값
int delta_row[] = {-1, 1, 0, 0}; // 행 변화량 (상: -1, 하: +1, 좌우: 0)
int delta_col[] = {0, 0, -1, 1}; // 열 변화량 (상하: 0, 좌: -1, 우: +1)
coord_queue는 큐의 역할을 하며, 각 요소는 {행, 열} 형태의 좌표를 저장합니다. parent_coord는 {이전_행, 이전_열}을 저장하여 도착 지점에서 시작 지점까지 경로를 역으로 찾아갈 수 있게 합니다.
BFS 탐색 함수: find_shortest_path_bfs
이 함수는 시작점에서 도착점까지의 최단 경로 존재 여부를 탐색합니다. 경로를 찾으면 true를 반환하고, 찾지 못하면 false를 반환합니다.
bool find_shortest_path_bfs() {
int queue_head = 0; // 큐의 앞 포인터 (원소 추출 위치)
int queue_tail = 0; // 큐의 뒤 포인터 (원소 삽입 위치)
// 시작 지점을 큐에 추가하고 방문 처리
coord_queue[queue_tail][0] = start_row;
coord_queue[queue_tail][1] = start_col;
queue_tail++;
visited_status[start_row][start_col] = true;
while (queue_head < queue_tail) {
// 큐에서 현재 위치 추출 (dequeue)
int current_r = coord_queue[queue_head][0];
int current_c = coord_queue[queue_head][1];
queue_head++; // 큐의 헤드 이동
// 현재 위치가 도착 지점인지 확인
if (current_r == end_row && current_c == end_col) {
return true; // 최단 경로 발견
}
// 4가지 방향 (상, 하, 좌, 우) 탐색
for (int i = 0; i < 4; i++) {
int next_r = current_r + delta_row[i];
int next_c = current_c + delta_col[i];
// 다음 위치의 유효성 검사 (미로 범위 내에 있는지)
if (next_r >= 0 && next_r < num_rows &&
next_c >= 0 && next_c < num_cols) {
// 이동 가능한 칸이고 아직 방문하지 않았다면
if (maze_grid[next_r][next_c] == 1 &&
!visited_status[next_r][next_c]) {
visited_status[next_r][next_c] = true; // 방문 처리
// 경로 역추적을 위해 현재 위치를 다음 위치의 부모로 기록
parent_coord[next_r][next_c][0] = current_r;
parent_coord[next_r][next_c][1] = current_c;
// 다음 위치를 큐에 추가 (enqueue)
coord_queue[queue_tail][0] = next_r;
coord_queue[queue_tail][1] = next_c;
queue_tail++;
}
}
}
}
return false; // 도착 지점까지의 경로를 찾지 못함
}
경로 재구성 및 출력 함수: reconstruct_and_print_path
find_shortest_path_bfs 함수가 true를 반환하면, 이 함수를 사용하여 parent_coord 배열에 저장된 정보를 바탕으로 실제 경로를 재구성하고 출력합니다.
void reconstruct_and_print_path() {
int path_trace[MAX_DIM * MAX_DIM][2]; // 경로를 저장할 임시 배열
int path_len = 0;
int current_r = end_row;
int current_c = end_col;
// 도착 지점에서 시작 지점까지 역으로 추적
while (!(current_r == start_row && current_c == start_col)) {
path_trace[path_len][0] = current_r;
path_trace[path_len][1] = current_c;
path_len++;
// 이전 부모 좌표를 가져옴
int prev_r = parent_coord[current_r][current_c][0];
int prev_c = parent_coord[current_r][current_c][1];
current_r = prev_r;
current_c = prev_c;
}
// 시작 지점 추가
path_trace[path_len][0] = start_row;
path_trace[path_len][1] = start_col;
path_len++;
// 경로를 시작 지점부터 도착 지점까지 역순으로 출력
printf("최단 경로: ");
for (int i = path_len - 1; i >= 0; i--) {
printf("(%d, %d) ", path_trace[i][0], path_trace[i][1]);
}
printf("\n");
}
시간 및 공간 복잡도 분석
미로의 크기를 M행 N열이라고 할 때:
- 시간 복잡도(Time Complexity): BFS는 최악의 경우 미로의 모든 칸을 한 번씩 방문하게 됩니다. 각 칸에 대해 인접한 최대 4개의 칸을 확인하므로, 전체 시간 복잡도는 O(M * N)이 됩니다.
- 공간 복잡도(Space Complexity):
visited_status,coord_queue,parent_coord배열이 미로의 크기에 비례하여 공간을 사용합니다. 따라서 공간 복잡도는 O(M * N)이 됩니다.
BFS의 적용 범위
BFS는 최단 경로 탐색 외에도 다양한 문제에 활용될 수 있습니다. 특히 각 노드 간의 이동 비용이 동일한 비가중치 그래프에서 최단 경로 또는 최소 단계 문제를 해결하는 데 매우 효과적입니다. 만약 노드 간 이동 비용이 다른 가중치 그래프에서 최단 경로를 찾아야 한다면, 다익스트라(Dijkstra) 알고리즘과 같은 다른 알고리즘을 고려해야 합니다.