너비우선탐색(BFS)란?
그래프의 탐색 방법 중 하나인, 너비우선탐색은 그래프의 한 정점을 방문한 후. 다음 방문정점으로 현재 정점과 인접해있으면서 아직 방문하지 않은 정점을 순차적으로 탐색하는 기법입니다.
트리의 너비우선탐색을, 각 노드마다 순서대로 방문하는 번호를 그림으로 표현한 것입니다.
DFS는 어느 한 노드가 무한에 가까운 깊이를 가지고 있을 때. 빠져나오지 못하는 문제가 발생할 수 있지만, BFS는 순차적으로 인접 노드를 방문하기 때문에 무한 루프에 빠질 가능성이 낮습니다.
이러한 BFS는 최단 경로를 찾는 데 효과적이며, 일반적으로 메모리를 더 많이 사용하는 경향이 있습니다. 반면에 DFS는 스택 자료구조를 사용하므로 메모리 사용이 상대적으로 적습니다.
BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 효율적인 탐색방법이며, 너비우선탐색은 선입선출 방식으로 탐색하므로 Queue 자료구조를 이용하여 구현합니다.
1과 0을 담은 이중 배열에서 0,0에서 3,3 좌표를 찾아가는 방문 순서입니다.
붉은색으로 칠해진 부분은 이미 방문한 좌표이며.
코드 상에서는 맵과 동일한 사이즈로 초기화된 visited 배열로 표현됩니다.
현재 좌표를 기준으로 위, 아래, 오른쪽, 왼쪽을 차례대로 방문해보면서 방문할 수 있는 지역을
(값이 1이면서 visited가 false인)
차례차례 찾아가면서 최단 경로를 찾는 알고리즘입니다.
코드 구현
주어진 문제는 1과 0으로 이루어진 미로를 빠져나오는 문제입니다.
출발지는 0,0 좌표로 시작되고 목적지는 맵의 끝지점인 N,M에 해당됩니다.
즉, 좌측최상단에서 시작하여, 우측최하단에 도착하는 것이 목표입니다.
이러한 이중배열에 해당하는 최단경로 탐색 문제에는 BFS 알고리즘을 사용하는 것이 일반적입니다.
BFS의 구현을 위해 필요한 배열은 세 가지입니다.
첫 번째는 전체 맵을 저장하기 위한 배열.
두 번째는 방문 노드르 저장하기 위한 배열.
세 번째는 노드의 방문 횟수를 저장하기 위한 배열.(정답을 위한 dp 배열)
먼저 mian함수에서는 필요한 데이터들을 input 받습니다.
미로의 전체 크기(배열 크기)에 해당하는 N과 M을 받고 맵에 해당하는 값들을 지도를 담는 배열에 저장합니다.
bfs함수에서는 탐색에 필요한 큐 자료구조와 방문 지역을 저장할 visited 배열, 경로값을 저장할 배열인 movePointSave 배열을 초기화합니다.
moverX와 moverY는 인접 정점으로 움직일 수 있도록 x,y 좌표의 이동 벡터를 담은 배열입니다.
예를 들어 x가 0, y가 1이라면 y방향으로 움직일 수 있습니다. 즉 0,0 → 0,1이 되는 것입니다.
여기서는 4방위, 동서남북의 벡터를 담았으며.
코드에 따라서 8방위를 담는 것도 가능합니다.
이 경우 다음과 같이 구현될 것입니다.
int moveX[8] = {0,1,0,-1,1,1,-1,-1};
int moveY[8] = {1,0,-1,0,-1,1,-1,1};while문은 bfs의 실질적인 탐색을 구현한 부분입니다.
큐에 저장된 현재값. (que.front())을 가져와,
visited를 true로 바꿔 방문했음을 표시합니다.
그리고 que에서 현재값을 pop하여 무한루프에 빠지지 않도록 합니다.
for문에서는 앞서 초기화한 벡터 배열을 순회하면서, 현재 좌표를 기준으로 4방위로 움직여가면서 인접 정점을 방문해갑니다.
조건문을 이용하여, 만족하는 정점의 경우에는 큐에 push하여 다음 좌표를 찾아갈 수 있도록 해줍니다.
그리고 이전 경로의 이동값에 1을 누적하여 총 지나온 횟수를 갱신합니다.
최종적으로 현재 좌표가 도착지인 경우에,
dp에 저장된 경로를 반환하여 최소 방문 횟수를 출력할 수 있도록 합니다.
이것이 BFS 알고리즘의 기본적인 구현법입니다.
이렇듯 좌표를 찾는 것 말고도, 트리의 각 노드를 순회하는 것도 가능하며 조건문을 적절히 수정하여, 다양한 값을 구하는 것이 가능합니다.
