[Java] 너비 우선 탐색 BFS 대하여 알아보자

2021-02-11

---

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. (출처 위키피디아)

---

사실 말은 조금 어려울 수 있어 그림으로 다시 한번 설명하겠다. 아래의 예제를 보자.

 

 

BFS로 1번 정점부터 시작해 탐색을 진행해 보겠다. 순서는 아래와 같다. 

 

1 - > 1번 정점이 큐에 들어가게 된다.

 

2 - > 1번 정점과 인접해 있는 두 개의 접점 2번과 4번 정점을 큐에 담는다.

 

3 - > 1번 정점과 인접한 곳이 더 이상 없기 때문에 그 이후에 큐에 들어온 2번 정점과 인접한 곳을 찾는다.

 

4 - > 2번 정점은 1, 3, 4 모두 인접해 있지만, 1번과 4번 정점은 기존에 탐색이 완료되었기 때문에 아직 탐색이 되지 않은 3번 정점이 큐에 들어온다.

 

5 - > 결과적으로 해당 정점의 BFS 탐색 순서는 1, 2, 4, 3의 순서가 된다. 

---

이를 코드를 구현하면 아래와 같은데, 입력받아야 하는 값은 정점의 개수와 / 이 정점들 간의 연결되어 있는 간선의 수 / 이 간선들의 관계를 2차원 배열로 입력받아야 한다. (시작 지점을 입력하라고 하는데, 1을 입력해 주면 되면 된다.)

package BFS;

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

public class Bfs {

	static int nV; // 정점의 수
	static int nE; // 간선의 수
	static int [][] arr2d; // 정점간 연결관계 저장 배열
	static boolean [] check; // 방문한 정점 체크 배열

	static void bfs(int i) {
		Queue<Integer> q = new LinkedList<>();
		// 선입선출( 먼저들어온것이 먼저 나간다.)
		// 의 특징을 가지는 큐를 활용해서 bfs 탐색을 시작
		q.offer(i);
		// 처음 시작지점 큐에 넣는다.

		while(!q.isEmpty()) {
			// 큐에 있는 모든 정점에 방문할때까지 반복
			int temp = q.poll();
			// 큐에 있는 방문한 정점을 하나 빼줌
			System.out.println("방문한 정점은 -> " + temp + " ");
			for(int j = 1; j < nV + 1; j++) {
				if(arr2d[temp][j] == 1 && check[j] == false) {
					// 현재 정점에서 다음 j 에 정점과 연결되었는지 체크
					// 연결되었으며, 기존에 방문한 정점인지 체크
					q.offer(j);
					// 모두 참이면 해당 정점 큐에 넣어줌
					check[j] = true;
					// 큐에 들어가면 확정방문 정점이기 때문에
					// 방문배열 체크.
				}
			}
		}
	}


	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
	
		
		nV = scan.nextInt(); // 정점입력
		nE = scan.nextInt(); // 간선입력
		
		arr2d = new int [nV+1][nV+1];
		check = new boolean [nV+1];
		// 0이 아닌 1부터 비교할 거기 때문에 
		// 모두 1씩 더해줌
		
		for(int i = 0; i < nE; i++) {
			int temp1 = scan.nextInt();
			int temp2 = scan.nextInt();
			
			arr2d[temp1][temp2] = arr2d[temp1][temp2] = 1;
			// 간선간의 연결관계 체크 양방향 모두 체크
		}
		
		System.out.println("탐색시작위치 입력 - > ");
		int start = scan.nextInt();
		bfs(start);
	}

}
//입력예제
//4 4
//1 2
//1 4
//2 3
//3 4
//
//1

 

이해를 돕기 위해 코드마다 모두 주석을 달아두었다. 콘솔에 입력 후 출력 결과를 확인하면 아래와 같다.