[Kotlin] 깊이 우선 탐색 - DFS, Depth-First Search

🔷 깊이 우선 탐색(DFS, Depth-First Search)란?

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

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

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

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

---

🔷 깊이 우선 탐색의 특징

🔹순환  알고리즘

        자기 자신을 호출하는 순환 알고리즘의 형태를 가진다.

🔹전위 운행  (Pre-Order Travels)

    시작 노드에서 아직 방문이 안 된 인접 분기로 넘어가는 형태는 전위 운행 트리 탐색 방법과 유사하다.

🔹방문 여부 확인

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

---

🔷 구현

🔹코틀린 (Kotlin)

/*
	node : Int = 현재 위치
    visited : BooleanArray = 방문 여부
    tree : Array<MutableList<Int> = 탐색할 트리
*/

fun dfs (node : Int){
	// 현재 노드 방문 확인
	visited[node] = true
    
    // 현재 노드를 기점으로 분기(branch) 확인
	tree[node].forEach { next ->
    	// 가장 인접한 미방문 노드 확인
		if(!visited[next]) dfs(next)
	}
}