이전 포스팅에서 DFS에 대해 공부하고 이번 포스팅에서는 BFS에 대해서 공부해보겠다 !!
BFS(너비 우선 탐색)의 탐색 순서는 다음과 같이 동작한다. 쉽게 말해, 한 단계씩 모든 인접한 노드를 먼저 탐색하고, 그 다음 단계로 넘어가서 다시 모든 인접한 노드를 탐색하는 방식이다. 깊이 우선 탐색(DFS)과는 다르게, 먼저 방문한 노드를 기준으로 가까운 거리부터 탐색해 나가는 알고리즘이다.
그림을 통해 BFS를 쉽게 설명해보겠다!
위에서 설명했듯이, BFS는 너비 우선 탐색이다. 즉, 한 단계씩 인접한 노드를 모두 탐색하고, 그다음 단계로 넘어가는 방식이다. 그림을 설명해보자!
- A에서 시작한다. 다시 한번 생각해보자, “너비 우선 탐색”.
- A의 자식노드 B, C, D를 모두 탐색한다.
- B, C, D의 자식 노드들을 탐색한다.
- B의 자식노드 E, C의 자식노드 F, D의 자식노드 G를 탐색한다.
- 더 이상 자식 노드가 없으므로 탐색이 종료된다.
이렇게 BFS는 가까운 노드부터 하나씩 모두 탐색하고 다음 단계로 넘어가며 탐색을 진행한다.
하지만 여기서 주의할 점! ! !
- ** 탐색한 노드는 건너뛰고, 중복을 피하기 위해 노드를 탐색할 때마다 탐색 여부를 체크한다. ***
이제 코드를 통해 알아보자!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입력을 빠르게 받기 위해 BufferedReader 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 줄에서 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 V를 입력받음
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 정점의 개수
int m = Integer.parseInt(st.nextToken()); // 간선의 개수
int start = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호
// 인접 리스트를 초기화 (정점이 1번부터 시작하므로 n+1 크기로 생성)
ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
// 방문 여부를 체크할 배열 (정점이 1번부터 시작하므로 n+1 크기로 생성)
boolean[] visited = new boolean[n + 1];
// 간선 정보를 입력받아 그래프를 구성 (양방향 간선)
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()); // 간선의 시작 정점
int v = Integer.parseInt(st.nextToken()); // 간선의 끝 정점
graph[u].add(v);
graph[v].add(u);
// 예를들어 u = 4, v = 3 일때, 4번 노드와 3번 노드는 양방향으로 연결돼있다.
// 따라서 실질적으로 노드와 간선을 그리는 부분이다.
}
// 각 정점의 인접 리스트를 정렬하여 방문 순서가 작은 번호부터 이루어지도록 설정
for (int i = 1; i <= n; i++) {
Collections.sort(graph[i]);
}
// BFS 탐색 결과를 저장할 StringBuilder
StringBuilder bfsResult = new StringBuilder();
// 큐를 사용하여 BFS 구현
Queue<Integer> queue = new LinkedList<>();
queue.offer(start); // 시작 정점을 큐에 넣음
visited[start] = true; // 시작 정점을 방문 처리
// BFS 탐색 시작
while (!queue.isEmpty()) {
// 큐의 첫 번째 노드를 꺼냄
int currentNode = queue.poll();
bfsResult.append(currentNode).append(" "); // 방문 노드를 결과에 추가
// 현재 노드의 인접한 노드들을 탐색
for (int neighbor : graph[currentNode]) {
if (!visited[neighbor]) { // 방문하지 않은 노드만 큐에 추가
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
// BFS 결과 출력
System.out.println(bfsResult.toString());
}
}
이 코드를 통한 전체적인 플로우를 작성해보았다!
- 정점(N), 간선(M), 탐색 시작 정점(V)을 입력받는다.
- 그래프를 인접 리스트 형태로 초기화한다. (ArrayList 배열 생성)
- 방문 여부를 체크할
boolean배열을 초기화한다. - 간선 정보를 입력받아 그래프를 구성하고, 양방향 간선을 추가한다.
- 각 정점의 인접 리스트를 오름차순으로 정렬하여 방문 순서가 작은 번호부터 탐색하도록 설정한다.
- BFS 탐색 결과를 저장할
StringBuilder를 생성하고, BFS를 위한 큐를 초기화한다. - 시작 정점을 큐에 넣고 방문 처리를 한 후, 큐가 비어있지 않을 동안 BFS 탐색을 진행한다.
- 큐의 첫 번째 노드를 꺼내어 현재 노드로 설정하고, 탐색 결과에 추가한다.
- 현재 노드의 인접한 노드들을 순서대로 큐에 추가하고, 방문 처리를 한다.
- 큐가 빌 때까지 반복한 후, 탐색 결과를 출력한다.
재귀를 통한 DFS와 BFS의 차이
DFS는 재귀 호출이나 스택을 이용하여 깊이 우선으로 탐색하는 반면, BFS는 큐를 사용하여 너비 우선으로 탐색한다. 각 알고리즘의 특성을 이해하고, 문제 상황에 맞는 알고리즘을 사용하여 효율적인 탐색을 수행해 보자!
이제 BFS 문제를 열심히 풀어보자 !!!!
