알고리즘 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

BFS (너비 우선 탐색)

---

BFS의 장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
• 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
• 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
• 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

BFS의 단점

• 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
• 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

BFS 구현

Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다.

1. Queue에서 하나의 노드를 꺼냅니다.
2. 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다.

/* BFS 코드 구현 */
public void bfs(Node root) {
    Queue<Node> qu = new LinkedList<Node>();
    Node temp = root;
    qu.add(temp);

    while(!qu.isEmpty()){
    
        /* 큐에서 뽑아서 바로 출력 시킨다. */
        temp = qu.poll();
        System.out.println(temp.value + " -> ");

        if(temp.left != null)	// temp.left가 있으면 큐에 추가.
            qu.add(temp.left);
        if(temp.right != null)
            qu.add(temp.right);	// temp.right가 있으면 큐에 추가.
    }
}

 

boolean 배열 visit로 해당 노드의 왼쪽, 오른쪽 노드를 방문했는지 체크 하면서 탐색하는 방법도 있다.

/* 내가 짠 코드 */
public void bfs(Node node) {
        Queue<Node>  qu = new LinkedList<Node>();
        boolean[] visit = {false,false};
        Node temp = this.root;
        qu.add(temp);

        while(!qu.isEmpty()){
            temp = qu.peek(); // qu에서 하나를 뽑는다.

            if(!visit[0]){
                if(temp.left != null) {
                    qu.add(temp.left);
                    visit[0] = true;
                }else{
                    System.out.print(qu.poll().value + " -> ");
                }
            }else if(!visit[1]){
                if(temp.right != null) {
                    qu.add(temp.right);
                    visit[1] = true;
                }else{
                    System.out.print(qu.poll().value + " -> ");
                }
            }else if(visit[0] && visit[1]){
                visit[0] = false;
                visit[1] = false;
                System.out.print(qu.poll().value + " -> ");
                temp = qu.peek();
            }
        }
    }

 

DFS (깊이 우선 탐색)

---

DFS의 장점

• 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있는 경우 빠르게 구할 수 있다.
• 구현이 너비 우선 탐색(BFS) 보다 간단하다.

DFS의 단점

• 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느리다.
• 결과 값이 없는 경로에 깊이 빠질 가능성이 있다.

DFS 코드 구현

• 중위순회(In-order) 방식과 동일

/* DFS 코드 구현 */
public void dfs(Node node) {
    if(node != null) {
        dfs(node.left);
        System.out.println(node.value + " -> ");
        dfs(node.right);
    }
}

📄 REFERENCES

---

coding-factory.tistory.com/611?category=794828

coding-factory.tistory.com/612

www.notion.so/Live-Study-5-75f857b63e524d33914a8b3ec6e1e894

coding-factory.tistory.com/612