[Algorithm] BFS(Breadth-first search)를 Java로 구현해보자!

---

안녕하세요 코딩노잼입니다.

오늘은 BFS(너비 우선 탐색)을 Java로 구현해보겠습니다.

 

1. BFS (Breadth-first Search)

BFS는 너비 우선 탐색이라고 부르기도 하며, 코딩 테스트에서 자주 등장하는 알고리즘 중에 하나입니다.

기본적으로 그래프 탐색에 사용되며, 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

BFS는 큐(Queue) 자료구조를 사용해서 구현할 수 있습니다.

글로만 보면 이해가 어려우실 테니 그림과 같이 보겠습니다.

그래프 예시

 

위와 같은 그래프가 존재하고 노드의 탐색은 1번부터 시작한다고 가정해보겠습니다.

  1. 큐에 1번 노드를 넣고 방문 처리합니다.

     (여기서 방문처리라는 것은 내가 해당 노드에 방문했음을 기록하는 것입니다.)

  2. 1번 노드와 가까운 노드를 큐에 넣고 방문 처리합니다. (2번, 3번 8번 노드)

     (어떻게 넣어도 상관은 없습니다. 저는 오름차순으로 넣겠습니다.)

  3. 큐에서 노드를 하나 꺼냅니다.

  4. 연결된 노드가 없으면 3번으로 다시 돌아갑니다.

  5. 연결된 노드가 있고 방문하지 않았으면 큐에 넣고 방문처리 후 3번으로 돌아갑니다.

  6. 연결된 노드가 있지만 방문을 이미 한 경우에는 3번으로 돌아갑니다.

  7. 3~6을 큐가 빌 때까지 반복하며 큐가 비었으면 종료합니다.

이러한 순서로 BFS를 진행하면 위의 그래프에서 탐색 순서는 다음과 같습니다.

  1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7

BFS알고리즘은 각 노드 간의 간선의 길이가 동일할 경우 최단거리를 구하는 알고리즘으로도 사용할 수 있습니다.

 

 

2. Java로 BFS 구현

사실 BFS자체는 구현하는 자체가 어렵지는 않습니다.

그러나 실제 코딩 테스트 문제를 풀어보면 단순히 구현하는 것보다 구현 과정에서 문제 해결을 위해 코드가 추가되거나 응용해서 생각해야 하는 부분들이 있기 때문에 구현을 할 수 있다면 깊이 있게 이해하기 위해 문제를 풀어보시는 것을 추천드립니다!

 

그럼 코드로 구현해보겠습니다.

package study.blog.codingnojam;

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() ;
	}
}

 

코드에 대부분의 설명을 위한 주석을 달아놓았으니 주석을 쭉 읽어보시면 이해하실 수 있을 겁니다.

위의 예시로 보여준 그림을 바탕으로 예제를 작성했고 실행하면 처음에 살펴본 것처럼 동일한 순서로 탐색이 이루어지는 것을 알 수 있습니다.

추가적으로 위와 같은 방식 말고 Node라는 클래스를 하나 만들어서 Node마다 연결된 정보를 가지고 있으면 Node배열을 통해서도 구현이 가능합니다.

실제 위와 같은 구현은 가장 기본적인 BFS를 위한 구현이고, 주어진 문제를 해결하기 위해서는 이를 응용해서 코드를 작성해야 합니다.

이런 부분은 다음에 실제로 코딩 테스트 문제를 풀어보면서 설명드리는 방식으로 포스팅을 진행하겠습니다.

---