너비 우선 탐색(Breadth First Search)
탐색 알고리즘의 하나인 BFS는 Breadth First Search의 약어로 우리말로 하면 너비 우선 탐색이다.
대표적인 탐색 알고리즘은 DFS와 BFS가 있는데 BFS는 선택 노드를 시작으로 인접한 노드(1세대)를 모두 탐색한 후 인접한 노드(1세대)와 인접한 노드(2세대)를 탐색하며 시작 노드부터 연결된 모든 노드를 탐색하는 기법이다. 시작 노드부터 시작 노드와 연결된 모든 노드를 탐색하기 때문에 세대가 같거나 비슷한 노드를 찾을 때 유리한 탐색 기법이며 BFS를 응용하여 최단 경로 탐색에도 적용할 수 있다. 이러한 특징으로 인해 가중치가 없는 정점 간격이 동간격인 네트워크에서 주로 활용되었다.
인접리스트를 탐색함에 있어, N개의 정점과 E개의 간선을 갖는 무방향 그래프에서 탐색에 걸리는 시간은 O(N + E)이다.
BFS의 의사 코드는 다음과 같다.
기본 개념
기본 개념은 다음과 같다.
1. 시작 정점(v) 선택
2. 시작 정점과 인접한 정점 수집(1세대)
3. 인접한 정점(1세대) 순회
4. 인접 정점(1세대)의 인접 정점(2세대) 수집
6. 인접한 정점(2세대) 순회
7. 목적지까지 도달하거나 전부 순회할 때까지 반복 진행
BFS는 기본적으로 같은 세대에 있는 노드를 모두 탐색 후 다음 세대를 탐색하기 때문에 진행 중인 세대의 탐색이 끝나기 전에 다음 세대를 만나더라도 진행 중인 세대를 모두 탐색한 후 다음 세대를 탐색할 수 있도록 선입선출(FIFO) 자료 구조인Queue 자료 구조를 많이 활용한다.
코드 구현
예제는 x, y 좌표로 구성된 공간에서 선택한 노드로부터 연결된 모든 노드의 이동 기대값을 구하는 예제이다.
public class BFSSampleCode{
private static final int[] dx = {-1, 0, 1, 0};//방향 벡터
private static final int[] dy = {0, 1, 0, -1};//방향 벡터
private int n, m = 0; //최대 x, y 좌표
private final Queue<Node> queue = new LinkedList<>();
private int[][] map;
private boolean[][] visited; //방문 여부 체크
private int[][] dis;
public BFSSampleCode(int[][] map){
this.map = map;
this.n = map.length;
this.m = map[0].length;
this.visited = new boolean[n][m];
this.dis = new int[n][m];
}
public void initialize(int start_x, int start_y){
visited[start_x][start_y] = true;
queue.offer(new Node(start_x, start_y));
}
public void bfs(int start_x, int start_y) {
initialize(start_x, start_y);
while (!queue.isEmpty()) {
Node tmp = queue.poll();
for (int i = 0; i < 4; i++) { // 위, 아래, 왼쪽, 오른쪽 4방향 인접 노드 탐색
int nx = tmp.x + dx[i]; //인접 노드 x 값
int ny = tmp.y + dy[i]; //인접 노드 y 값
if (nx < 0|| nx >= n || ny < 0 || ny >= m) { //유효 범위 이탈 방지
continue;
}
if(map[nx][ny] == 1){ // 1(벽)일 경우 패스
continue;
}
//이미 방문된 경우 스킵
if (visited[nx][ny]) {
continue;
}else{
visited[nx][ny] = true; //방문하지 않은 경우 방문 체크
}
dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
queue.offer(new Node(nx, ny)); //방문할 인접 노드의 인접 노드 추가
}
}
print();
}
public void print(){
for(int[] row: dis){
for (int col : row) {
System.out.print(col + " ");
}
System.out.println();
}
}
static class Node {
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
int[][] map = new int[][]{{0, 0, 0, 0, 0}
, {0, 0, 1, 1, 0}
, {0, 0, 1, 0, 0}
, {0, 0, 1, 0, 0}
, {1, 0, 0, 0, 0}};
BFSSampleCode bfs = new BFSSampleCode(map);
bfs.bfs(1, 1);
}
}
Reference.
이경훈, 오창주.(2002).BFS 알고리즘을 이용한 차단밸브의 최적 선정 모형에 관한 연구.한국수자원학회 분과위원회 연구과업보고회,(),59-80.
신현준. "스마트 팩토리에서 제조라인 신뢰성 향상을 위한 기계학습 기반의 이상상황 진단 및 동적 라우팅 방안." 국내박사학위논문 한국기술교육대학교, 2018. 충청남도