[알고리즘] 너비 우선 탐색( Breadth First Search, BFS)

너비 우선 탐색 : 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

​

' 맹목적인 탐색 ' 을 하고자 할 때 사용할 수 있는 탐색 기법으로 ' 최단 경로 ' 를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용

​

※ 시작점과 거리가 멀수록 탐색이 느려진다. 하지만 근처에 있을 경우 빠르게 탐색 가능하다.

※ 맹목적인 탐색 : 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 탐색하는 방법을 말한다.

​

너비 우선 탐색을 하기 위해서 필요한 준비물은 Queue ( 큐 ) 이다.

​

우선 어떤식으로 정렬이 이루어 지는지 보자면!

다음과 같이 1 2 3 4 5 가 서로 연결되어 있다고 보았을 때 너비 우선 탐색을 해보자면

시작 노드 ( Start Node ) 를 큐에 삽입해 주고 시작한 노드는 방문 했다는 뜻으로 ' 방문처리 ' 를 해줍니다.

방문처리는 주황색으로 하였습니다.

그후 시작 노드 1을 큐에서 꺼내고, 시작 노드의 주변 노드인 2와 3 모두 방문한 적 없기 때문에 큐에 넣어줍니다.

다음으로 2를 큐에서 꺼내고 2와 연결된 3과 4중 3은 이미 큐에 포함되어 있으므로 4만 큐에 추가시키고

방문 처리를 해줍니다.

다음으로 3도 마찬가지로 큐에서 꺼내주고 연결된 주변노드 4를 확인합니다.

4는 이미 큐에 포함되어 있기 때문에 그 외 다른 작업은 하지 않습니다.

4를 큐에서 꺼내면서 인접한 주변 노드 5를 확인하여 큐에 없기 때문에 큐에 넣어줍니다.

그후 5를 꺼내어 확인하여보면 1 2 3 4 5 순서대로 큐에서 꺼낸것을 확인할 수 있습니다.

​

이렇게 너비 우선 탐색은 아무렇게나 탐색하는 것이 아닌 시작 노드에서 ' 가까운 ' 노드들부터 탐색이 이루어집니다.

​

너비 우선 탐색을 C++ 코드로 구현해 본다면

#include <iostream>   // C++ 헤더
#include <vector>
#include <queue>

using namespace std;

int number = 5;
int c[5];
vector<int> a[5];

void bfs(int start) {
	queue<int> q;

	q.push(start);
	c[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d ", x + 1);
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!c[y]) {
				q.push(y);
				c[y] = true;
			}
		}
	}
}


int main(void) {
	a[0].push_back(1);  // 0 뒤에 1을 연결
	a[1].push_back(0);

	a[0].push_back(2);  // 0 뒤에 2를 연결
	a[2].push_back(0);

	a[2].push_back(1);
	a[1].push_back(2);

	a[1].push_back(3);
	a[3].push_back(1);

	a[2].push_back(3);
	a[3].push_back(2);

	a[3].push_back(4);
	a[4].push_back(3);

	bfs(0);
}

자바로 코딩을 해보자면

import java.util.Iterator;
import java.util.LinkedList;

public class Study_BFS {

	public static LinkedList<LinkedList<Integer>> list = new LinkedList<>();
	public static boolean [] arr = new boolean[5];
	
	public static void main(String[] args) {
		// TODO 자동 생성된 메소드 스텁	
		for(int i = 0; i < 5; i++)
			list.add(new LinkedList<Integer>());
		
		list.get(0).add(1);
		list.get(1).add(0);
		
		list.get(0).add(2);
		list.get(2).add(0);
		
		list.get(1).add(2);
		list.get(2).add(1);
		
		
		list.get(1).add(3);
		list.get(3).add(1);
		
		list.get(2).add(3);
		list.get(3).add(2);
		
		list.get(3).add(4);
		list.get(4).add(3);
		bfs(1);
	}
	
	static void bfs(int start) {
		
		int st = start -1;
		Queue<Integer> queue = new Queue<>();		
		
		queue.push(st+1);
		arr[st] = true;
		
		Iterator<LinkedList<Integer>> it = list.iterator();
		
		while(it.hasNext()) {
			
			queue.pop();
			
			for(int i = 0; i < list.get(st).size(); i++) {
				
				if(!arr[list.get(st).get(i)]) {
					queue.push(list.get(st).get(i)+1);
					arr[list.get(st).get(i)] = true;
				}
			}
			st++;
			it.next();
		}
	}
}

class Queue <T> {
	private int max = 0;
	private LinkedList<T> Queue;
	
	public Queue() {
		Queue = new LinkedList<T>();
	}
	
	public void push(T o) {
		Queue.add(o);
		max++;
	}
	
	public void pop() {
		max--;
		System.out.println(Queue.get(0));
		Queue.remove(0);
	}
	
	public int size() {
		return max;
	}
	
	public String toString() {
		return Queue.toString();
	}
}

BFS ( 너비 우선 탐색)는 너비를 우선으로 하여 탐색한다는 특성이 중요한 것이고, 이를 이용하여

다른 알고리즘에 적용한다는 것이 핵심입니다!!! BFS 자체는 큰 의미가 없다!