[Algorithm] Tree Traversal (Feat. BFS, DFS)

 

 

트리 순회 Skill

• 모든 트리를 순회하며 부모 정보를 갱신한다.
• Depth (높이) 정보도 갱신한다.

 

핵심 아이디어

사실 트리 자료구조는 그래프에서 Cycle 이 사라지고 계층 (부모-자식 관계)가 남은 것이므로 그래프 순회 이론을 거의 그대로 적용 가능하다.

 

 

부모 노드를 제외한
다른 모든 노드를 자식으로 갖는다.

 

모든 자식 노드의 depth는
부모 노드의 depth + 1 이다.

BFS 를 이용한 방법

// 부모를 담을 배열 parents 와
// 깊이를 보관할 배열 depths
// 인접 노드를 담은 adjacentList 만 필요하다.
private fun bfs(rootNode: Int, parents: IntArray, depths: IntArray, adjacentList: Array<LinkedList<Int>>) {

    val queue : Queue<Int> = LinkedList()
    queue.add(rootNode)

    while (queue.isNotEmpty()) {
        val curNode = queue.poll()
        for (adjacentNode in adjacentList[curNode]) {
        // 방문 노드가 내 부모인 경우 skip
            if (parents[curNode] == adjacentNode) continue
            parents[adjacentNode] = curNode // 다음 노드는 현재 노드의 자식
            depths[adjacentNode] = depths[curNode] + 1 // 부모 노드 깊이 + 1
            queue.add(adjacentNode)
        }
    }
}

 

DFS 를 이용한 방법

private fun dfs(curNode: Int, parentNode: Int, parents: IntArray, depths: IntArray, adjacentList: Array<LinkedList<Int>>) {
    for (nextNode in adjacentList[curNode]) {
        if (nextNode == parentNode) continue
        parents[nextNode] = curNode
        depths[nextNode] = depths[curNode] + 1
        dfs(nextNode, curNode, parents, adjacentList)
    }
}

 

 

BFS vs DFS 무엇을 사용할까?

재귀를 사용한 DFS 의 경우 코드 길이가 짧고 간결하다. 대신, 플랫폼에 따라서 Stack 메모리 초과 위험이 있다.

BFS 의 경우 코드가 좀 긴 대신, Stack 메모리 초과 위험이 거의 없다.

 

대부분의 경우엔 BFS 사용을 권장한다.

단, 구현하는데 최대한 시간을 절약할 필요가 있다면 DFS 를 익혀두고 사용하자.