안녕하세요 오늘은 BFS에 대해 알아보겠습니다. BFS는 Breadth First Search의 약자이며, 너비 우선 탐색이라고 부릅니다. 루트 노드나 임의의 노드에서 시작하여 인접한 노드를 먼저 모두 확인한 후 다음 depth를 탐색합니다. Queue를 사용하여 데이터를 탐색합니다.
1. BFS (Breadth First Search)의 장점과 단점
너비 우선 탐색은 최대한 넓게 이동 후 더 이상 갈 수 없을 경우 아래로 이동합니다. 거리가 가까운 정점을 먼저 탐색하고, 가장 멀리 떨어져 있는 정점을 가장 나중에 방문합니다. BFS는 재귀적으로 동작하지 않습니다.
● 장점
모든 경로를 탐색하기에 여러 해가 있을 경우에도 최단 경로임을 보장합니다.
최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있습니다.
● 단점
최소 실행 시간보다는 오래 걸린다는 것이 거의 확실합니다.
최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있습니다.
2. BFS의 흐름
BFS의 대표적인 그림입니다. 각 노드는 정점(Vertex)를 표현하는 것이고, 선은 간선(Edge)이며 각 정점을 연결합니다.
만약 시작 정점이 0번일 경우, BFS는 숫자가 낮은 부분부터 탐색을 합니다. 설계하는 사람에 따라 다르지만, 일반적으로는 숫자가 낮은 정점부터 탐색을 합니다.
0번에서 1번을 탐색합니다. 큐에는 1이 들어갑니다. 큐에서 1번을 빼고, 1과 연결된 2번과 3번을 넣습니다. 큐에 2번을 빼고, 2번과 연결된 4번과 5번을 넣습니다. 이번에는 3번을 빼고 6번을 넣습니다. 이미 방문한 곳은 탐색할 필요가 없으므로 4번, 5번, 6번을 순차적으로 뺍니다.
3. Queue를 활용한 BFS의 예제
① 2차원 배열 선언
import java.util.LinkedList;
import java.util.Queue;
public class BfsExam {
public static void main(String[] args) {
int[][] graph = {{}, {2,3,3}, {1,6,3}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
boolean[] visited = new boolean[9];
System.out.println(bfs(1, graph, visited));
}그래프를 2차원 배열로 표현했습니다. 배열의 인덱스를 노드와 매칭 시켜 사용하기 위해 0번 인덱스는 아무것도 저장하지 않습니다. 방문을 했는지 표시하기 위해 boolean 타입 배열을 선언했습니다. 출력문은 1 → 2 → 3 → 8 → 6 → 5 → 4 → 7이라고 예상됩니다.
② 탐색과 큐 생성
static String bfs(int start, int[][] graph, boolean[] visited) {
StringBuilder sb = new StringBuilder();
Queue<Integer> q = new LinkedList<Integer>();
q.offer(start);
visited[start] = true;탐색 순서를 출력하기 위해 객체를 만들어주고, BFS에 넣을 큐를 생성했습니다. 마지막 줄 코드는 시작 노드 방문 처리를 하는 코드입니다.
③ 노드 확인
while(!q.isEmpty()) {
int nodeIndex = q.poll();
sb.append(nodeIndex + " -> ");
for(int i=0; i<graph[nodeIndex].length; i++) {
int temp = graph[nodeIndex][i];
if(!visited[temp]) {
visited[temp] = true;
q.offer(temp);
}
}
}
return sb.toString() ;
}
}큐에서 꺼낸 노드와 연결된 노드를 체크하는 코드입니다. 만약 방문하지 않았다면 방문 처리 후에 큐에 넣습니다.
4. 실행 결과
정상적으로 실행이 잘 됐습니다.
