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