[Kotlin] 넓이 우선 탐색 - BFS, Breadth-First Search

🔷 넓이 우선 탐색(BFS, Breadth-First Search)란?

[이미지 출처]https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

    시작 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 인접한 노드를 완벽하게 탐색하는 방법이다.

    아직 방문하지 않은 노드를 시작점으로 인접 노드를 계속 탐색한다.

    완벽하게 탐색을 한 상태가 되면(인접 노드를 다 방문한 후) 다음 분기로 넘어간다.

---

🔷 넓이 우선 탐색의 특징

🔹비순환  알고리즘

        깊이 우선 탐색과 달리 재귀 방식으로 작동하지 않는다.

🔹비직관적

        넓게 퍼지면서 검색하는 방식으로 직관직이지 않다.

🔹선입선출 (FIFO)

    방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

    🔹 Queue 게시글 확인하기

🔹방문 여부 확인

     모든 노드를 방문하여 방문 여부를 확인해야한다. 미확인 시 무한 루프에 빠질 수 있다.

---

🔷 구현

🔹코틀린 (Kotlin)

/*
    node : Int = 현재 위치
    visited : BooleanArray = 방문 여부
    tree : Array<MutableList<Int> = 탐색할 트리
    queue : LinkedList<Int>() = 인접 노드
*/

// Queue 구조를 위한 import
import java.util.LinkedList

fun bfs(node: Int) {
	// queue와 방문 리스트에 추가
	queue.add(node)
	visited[node] = true
	
    // 인접 노드 확인
	while (queue.isNotEmpty()) {
		val head = queue.poll() // 첫 원소 반환 후 remove
		
        // 현재 노드를 기점으로 인접 노드
		for (next in tree[head]) {
        	// 방문 여부 확인
			if (!visited[next]) {
				visited[next] = true
				queue.add(next)
			}
		}
	}
}