[JAVA] 알고리즘 BFS [Breadth-First Search] 너비 우선 탐색
BFS [Breadth-First Search]는 너비 우선 탐색이며 너비를 우선적으로 탐색합니다.
2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 주변을 순차적으로 방문하여 모든 노드를 탐색하는 방법입니다.
모든 노드를 탐색하는 알고리즘으로 깊이 우선 탐색을 하는 DFS와는 달리 Stack을 이용하지 않으며 Queue를 이용하여 전개할 수 있습니다.
- DFS - 재귀, stack 자료 구조 활용
- BFS - Queue 자료 구조 활용
BFS를 코드로 구현하기 위해서 3가지를 우선적으로 구현해놓아야 합니다.
- 탐색할 2차원 배열 또는 그래프
- 방문처리를 하기 위한 boolean type
- Queue 자료 구조
|
|
static int[][] graph = {{}, {2, 3, 8}, {1, 6, 8}, {1, 5}, {5, 7}, {3, 4, 7}, {2}, {4, 5}, {1, 2}}; // 탐색할 그래프
static boolean[] visited = new boolean[graph.length]; // 방문처리를 위해 사용
static Queue<Integer> q = new LinkedList<>(); // Queue
|
cs |
graph는 탐색할 전체 노드의 구조입니다. visited는 방문처리를 위해 사용합니다. Queue는 너비 탐색을 하기위한 자료구조입니다.
Queue 자료구조를 모르신다면 Queue의 동작원리와 JAVA API를 통해 해당 클래스의 함수를 공부하고 보시길 바랍니다.
굳이 static으로 처리할 필요는 없습니다.
여러 함수에서 사용될 것이라 예상되면 매개변수로 넘겨주는 방법 대신에 클래스 변수로 처리하여
모든 함수에서 바로 사용할 수 있게끔 하는 편입니다.
앞서 선언된 3가지를 이용해서 BFS함수를 작성하도록 하겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static void BFS(int n){
q.offer(n); // 시작 지점
visited[n] = true;
while (!q.isEmpty()) {
int x = q.poll();
sb.append(x).append(" ");
for (int y : graph[x]) {
if (!visited[y]) {
q.offer(y); // 큐에 넣어서 저장이 됐으니.
visited[y] = true; // 해당 지점은 방문처리
}
}
}
}
|
cs |
BFS의 구현 코드 자체는 어렵지 않습니다.
2줄) BFS(int n)으로 넘어온 첫 방문 노드를 Queue에 넣어줍니다. 그럼 현재 Queue에는 첫 방문 노드가 입력되어 들어갑니다.
3줄) 첫 방문 노드는 Queue에 넣어두었으므로 방문처리를 처리해줍니다.
첫 방문 노드가 Queue에 있으므로, 이제부터 Queue가 빌 때까지 while 반복문을 돌려줄 수 있습니다.
5줄) while (! q.isEmpty()) 반복문의 종료 조건은 Queue가 비는 순간 종료됩니다.
6줄) 이제 반복문 안에서 Queue에 입력된 노드 하나를 poll() 함수를 통해 가져옵니다.
7줄) StringBuiler의 sb.append(x). append(" ")는 방문 순서를 BFS함수가 종료되고 난 후 출력을 보기 위함입니다.
9줄) for (int y : graph [x]) 현재 Queue에서 가져온 노드[x]와 연결되어있는 모든 노드들을 순차적으로 확인합니다.
10줄) if (!visited [y]) 만약 방문처리가 false라면 방문하지 않았다는 의미이므로
11줄) q.offer(y) Queue에 넣어줍니다.
12줄) visited[y] = true 해당 노드는 Queue에 들어가는 순간 방문처리를 해주어 다시 방문하지 않도록 처리합니다.
BFS가 너비탐색이 되는 이유는 Queue 자료구조의 특징인 먼저 들어간 요소가 먼저 나온다는 점 때문입니다.
첫 방문노드와 연결된 노드들을 반복문으로 Queue에 순차적으로 넣은 후 해당 노드들을 poll() 함수를 통해 가장 먼저 꺼내
우선적으로 처리하기 때문에 너비를 먼저 탐색하게 되는것입니다.
가장 최근에 방문처리한 노드는 Queue에서 순서가 맨 마지막에 있게 됩니다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import java.util.*;
public class BFS_graph {
static int[][] graph = {{}, {2, 3, 8}, {1, 6, 8}, {1, 5}, {5, 7}, {3, 4, 7}, {2}, {4, 5}, {1, 2}};
static boolean[] visited = new boolean[graph.length];
static Queue<Integer> q = new LinkedList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
System.out.print("방문순서: ");
BFS(1);
System.out.println(sb);
}
public static void BFS(int n){
q.offer(n);
visited[n] = true;
while (!q.isEmpty()) {
int x = q.poll();
sb.append(x).append(" ");
for (int y : graph[x]) {
if (!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
}
}
|
cs |