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

너비 우선 탐색 (BFS, Breadth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 

 

너비 우선 탐색은 현재 위치를 기준으로 사방으로 퍼져나가면서 탐색하는 방법으로, 

인접한 정점들을 먼저 탐색한 후에 차례로 탐색을 진행한다. 

 

장점

• 모든 가중치가 동일할 때, 시작 정점으로 부터 목표까지 최단 경로를 보장한다.

 

단점

• 정점의 수가 늘어날 수록 탐색에 불필요한 정점을 저장해야 하기 때문에 저장공간이 비교적 많이 필요하다.  

주로 두 정점 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다.

점점 탐색 범위를 확장하며 탐색하기 때문에 처음 발견하는 경로가 최단 경로가 된다. 

주의할 점은 DFS와 마찬가지로 방문 체크가 필요하다.

 

 

그림으로 이해하면 쉽기 때문에, 아래 그림의 트리와 그래프를 예시로 탐색 순서를 알아보자! 

 

 

위 그림과 같은 트리가 있을 때 BFS 탐색 순서는  A  - B - C - D - E - F - G - H - I - J 

순서에서 같은 높이의 노드를 같이 탐색하는 것을 볼 수 있다.

 

 

위 그림과 같은 방향 그래프에서는  A - B - C - G - E - D - F  가 된다.

방문 체크를 하지 않을 경우 E를 방문한 후에 A를 다시 방문하면서 불필요한 탐색을 하게 된다. 

 

구현 방법

BFS는 큐를 이용하여 구현할 수 있다. 

 

큐를 이용한 방법

트리라면 루트 노드, 그래프라면 임의의 정점에서 시작한다.

1. 시작 정점에 방문처리 후, 큐에 삽입한다.

2. 큐가 비어있을 때까지 아래의 동작을 반복

    1. 첫번째 원소 반환

    2. 인접한 정점에서 방문하지 않은곳을 큐에 넣고 방문 처리

        1번에서 반환하면서 방문 처리를 할 수 있지만, 삽입할 때 방문 처리를 하면 큐에 중복으로 삽입하는 횟수를 줄일 수 있다. 

        목표 정점이 존재할 경우 필요한 값을 저장 후 종료.

public static void bfs(int node) {
	visit = new boolean[V];
	queue.offer(node);
		
    while(!queue.isEmpty()) {
		int curr = queue.poll();
        
		if (!visit[curr]) {
			visit[curr] = true;
			System.out.print(curr+" ");

			for (int next = 0; next < V; next++) {
            
            	//목표 정점이 있을 경우
                if (next == 목표 정점 조건) {
                	//처리
                	return;
                }
            
				if (!visit[next] && graph[curr][next] == 1)
					queue.offer(next);
			}
		}
	}
}

 

 

BFS를 활용한 문제

[백준] 1260번: DFS와 BFS

[백준] 7576번: 토마토

[백준] 14502번: 연구소