BFS, DFS 알고리즘

📗 전역 클래스 Node

class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt = null;
        rt = null;
    }
}

---

📌 BFS

너비 우선 탐색(BFS, Breadth-First Search)

• 시작 정점 방문 후 가까운 정점 우선 방문
• 넓게 탐색하는 방법
• 두 노드 사이 최단 거리, 최단 경로를 구할 때 사용
• 장점 : 최적해 찾음 보장 / 단점 : 최소 실행보다 시간이 오래 걸림
• 큐(Queue)를 사용하여 선입선출 원칙으로 탐색

코드 설명

public class BFS {
    Node root;
    public static void main(String[] args) {
        BFS tree = new BFS();
        tree.root = new Node(0);
        tree.root.lt = new Node(1);
        tree.root.rt = new Node(2);
        tree.root.lt.lt = new Node(3);
        tree.root.lt.rt = new Node(4);
        tree.root.rt.lt = new Node(5);
        tree.root.rt.rt = new Node(6);
        tree.BFS(tree.root);
    }

public void BFS(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int L = 0;  // 계층 단위

        while (!q.isEmpty()) {
            int len = q.size();
            System.out.print(L + " : ");
            for (int i = 0; i < len; i++) {
                // 최근 큐에서 poll 되는 숫자 출력
                Node current = q.poll();
                System.out.print(current.data + " ");
                
                // 노드의 자식들을 큐에 삽입
                if (current.lt != null) {
                    q.offer(current.lt);
                }
                if (current.rt != null) {
                    q.offer(current.rt);
                }
            }
            L++;
            System.out.println();
        }
    }

• While문은 Queue가 비어있을 때까지 반복해서 돌아감
• 1단계
  • 현재 Queue에는 0 하나만 들어갔기에 len = 1
  • 출력 이후 lt, rt 노드 값을 Queue에 삽입
• 2단계
  • 현재 Queue에는 2개의 값 (1, 2) 존재
  • 출력 이후 각 값의 lt, rt Queue에 삽입

---

📌 DFS

깊이 우선 탐색(DFS, Dreadth-First Search)

• 시작 정점 방문 후 다음 분기로 넘어가기 전 해당 분기 완벽 탐색
• 깊게 탐색하는 방법
• 트리에서 보면 노드 방문 후 자식 노드 우선 방문
• 장점 : 최선의 경우 빠르게 해를 찾음 / 단점 : 최악의 경우 해를 찾는 시간이 오래 걸림

코드 설명

public class DFS {
    Node root;

    public static void main(String[] args) {
        DFS tree = new DFS();
        tree.root = new Node(0);
        tree.root.lt = new Node(1);
        tree.root.rt = new Node(2);
        tree.root.lt.lt = new Node(3);
        tree.root.lt.rt = new Node(4);
        tree.root.rt.lt = new Node(5);
        tree.root.rt.rt = new Node(6);
        tree.DFS(tree.root);
    }

    public void DFS(Node root) {
        if (root == null) {
            return;
        }
        else {
            System.out.print(root.data + " ");
            DFS(root.lt);
            DFS(root.rt);
        }
    }
}

• DFS는 대게 스택을 사용하고 모든 노든을 방문하고자 할 때 사용
• 1단계
  • DFS(tree.root) 호출로 DFS 인자값으로 0이 들어옴
  • 0은 null 아니기에 else를 타고 재귀 실행
• 2단계
  • 해당 값의 lt가 존재하지 않을 경우 return을 하는 백트래킹 시행

---