[알고리즘]그래프4 - BFS(feat. Java)

BFS란?

저번 글에서 알아본 DFS는 깊이 우선 탐색이었다면 BFS(Breadth-First Search) 너비 우선 탐색으로서 DFS와 함께 코딩 문제에 단골로 등장하는 그래프 탐색 알고리즘이다.

 

DFS는 제일 깊이 있는 노드까지 탐색한 뒤에 돌아오는 방식이면, BFS는 인접한 노드를 먼저 탐색을 하는 알고리즘이다. 그렇기 때문에 재귀(Stack 구조)를 활용하여 구현했던 DFS와 달리, BFS는 Queue를 통해 구현을 하게 되고 Queue를 생각하면 이해하는 것도 쉽습니다.

 

저번 시간에 다루었던 예제를 또 다루어보면,

 

 

• 1번 노드를 큐에 넣은 후 방문처리
• 큐에서 노드를 꺼낸 후 인접 노드를 큐에 넣고 방문 처리
• 바로 위의 과정을 반복
  
  • 1번 노드 꺼낸 후 2, 3, 8번 노드가 큐에 들어감 (Queue : 2, 3, 8)
  • 2번 노드 꺼낸 후 6번 노드가 큐에 들어감 (Queue : 3, 8, 6)
  • 3번 노드 꺼낸 후 5번 노드가 큐에 들어감 (Queue : 8, 6, 5)
  • 8번 노드 꺼냄 (Queue : 6, 5)
  • 6번 노드 꺼냄 (Queue : 5)
  • 5번 노드 꺼낸 후 4, 7번 노드가 큐에 들어감 (Queue : 4, 7)
  • 4번 노드 꺼냄 (Queue : 7)
  • 7번 노드 꺼냄 (Queue : )

결론적으로 탐색 순서는 1 -> 2 -> 3 -> 8 -> 6-> 5 -> 4 -> 7이다. BFS 알고리즘은 각 노드 간의 간선의 길이가 동일할 경우 최단 거리를 구하는 알고리즘으로도 사용될 수 있다.

 

 

 

코드 구현

BFS 는 Queue 자료 구조를 이용하여 구현하기 때문에 구현에는 크게 어려움이 없다.

 

하지만 코딩 테스트 문제의 경우, 단순히 BFS를 사용하는 것이 아닌 문제 해결을 위해서 여러 조건들을 추가하고 BFS를 응용하여야 풀 수 있는 문제들이 많기 때문에 기본적인 BFS의 작동 방식이나 구조를 확실히 이해하는 것이 중요하다.

 

import java.util.LinkedList;
import java.util.Queue;

public class StudyBFS {
	
	public static void main(String[] args) {
		
		// 그래프를 2차원 배열로 표현해줍니다.
		// 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않습니다.
		// 1번인덱스는 1번노드를 뜻하고 노드의 배열의 값은 연결된 노드들입니다.
		int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
		
		// 방문처리를 위한 boolean배열 선언
		boolean[] visited = new boolean[9];
		
		System.out.println(bfs(1, graph, visited));
		//출력 내용 : 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 -> 
	}
	
	static String bfs(int start, int[][] graph, boolean[] visited) {
		// 탐색 순서를 출력하기 위한 용도
		StringBuilder sb = new StringBuilder();
		// BFS에 사용할 큐를 생성해줍니다.
		Queue<Integer> q = new LinkedList<Integer>();
		 
		// 큐에 BFS를 시작 할 노드 번호를 넣어줍니다.
		q.offer(start);
		
		// 시작노드 방문처리
		visited[start] = true;
		
		// 큐가 빌 때까지 반복
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			sb.append(nodeIndex + " -> ");
			//큐에서 꺼낸 노드와 연결된 노드들 체크
			for(int i=0; i<graph[nodeIndex].length; i++) {
				int temp = graph[nodeIndex][i];
				// 방문하지 않았으면 방문처리 후 큐에 넣기
				if(!visited[temp]) {
					visited[temp] = true;
					q.offer(temp);
				}
			}
		}
		// 탐색순서 리턴
		return sb.toString() ;
	}
}