[알고리즘] DFS(깊이우선탐색)와 BFS(너비우선탐색)

• 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.
• 그래프란? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종
• 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

 

DFS(깊이 우선 탐색)

https://developer-mac.tistory.com/64

• 시작점에서 한 갈래로 더 이상 갈 수 없을 때까지 탐색하고, 더 갈 곳이 없다면 이전의 경로로 되돌아간다. 
• 가장 직관적이고 구현하기 쉬운 탐색 방법
• 현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복 
• 같은 정점을 다시 방문하지 않도록 정점에 방문했다는 것을 표시
• 스택이나 재귀함수를 통해 구현

 

DFS의 구현 - 재귀함수 

// 각 노드를 나타내는 클래스 정의
class TreeNode {
    int val;         // 노드의 값
    TreeNode left;   // 왼쪽 자식 노드
    TreeNode right;  // 오른쪽 자식 노드

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Tree {

    // DFS(깊이 우선 탐색) 구현 메서드
    public void dfs(TreeNode root) {
        // 종료 조건: 현재 노드가 null인 경우 함수 종료
        if (root == null) {
            return;
        }

        // 순회: 현재 노드를 방문한 후 왼쪽 서브트리, 오른쪽 서브트리 순으로 탐색
        System.out.println(root.val);  // 현재 노드의 값을 출력 
        dfs(root.left);                 // 왼쪽 서브트리를 DFS로 탐색
        dfs(root.right);                // 오른쪽 서브트리를 DFS로 탐색
    }

    // 메인 메서드
    public static void main(String[] args) {
        // 간단한 이진 트리 생성
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // DFS 수행
        Tree tree = new Tree();  // Tree 클래스의 객체 생성
        tree.dfs(root);          // 생성된 객체를 통해 DFS 메서드 호출
    }
}

• 왼쪽에 위치한 노드를 우선적으로 탐색
• 해당 위치의 노드가 null이라면, 이전 케이스로 돌아온다.
• 오른쪽에 위치한 노드를 탐색
• 이를 재귀적으로 반복

 

DFS를 적용하는 경우

DFS는 사이클(=순환)의 존재 여부를 확인할 때 사용

• DFS가 사이클 여부를 확인할 때 사용되는 이유는 깊이를 우선적으로 탐색하기 때문
• 즉, 하나의 방향이 잡히면 그 방향의 끝에 도달할 때까지 탐색하기 때문
• 사이클이 존재하는 방향만 찾으면 바로 사이클을 확인할 수 있다.

 

BFS(너비 우선 탐색)

https://developer-mac.tistory.com/64

• 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
  • 현재 위치를 기준으로 가장 가까운(=인접한) 노드를 순차적으로 방문
  • DFS와는 다르게 끝까지 파고들지 않고, 주변을 순차적으로 확인하는 방법
  • FIFO(선입선출)와 동일한 형태를 가짐

• 큐를 이용하여 구현
• 출발점을 먼저 큐에 넣고, 다음 로직을 반복
  • 큐에 저장된 정점을 하나 Dequeue
  • Dequeue된 정점과 연결된 모든 정점을 큐에 넣기
  • 큐가 비어있다면 반복을 종료

 

BFS의 구현 - Queue

- TreeNode 구현 생략

public class Tree {

    // BFS에 사용할 큐 선언
    static Queue<TreeNode> queue = new LinkedList<>();

    // BFS 구현 메서드
    public void bfs(TreeNode root) {
        if (root == null) {
            return;
        }

        // 시작 노드를 큐에 추가
        queue.offer(root);

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 노드 추출
            TreeNode current = queue.poll();

            // 현재 노드의 값을 출력 (또는 다른 처리 수행)
            System.out.println(current.val);

            // 왼쪽 자식이 있으면 큐에 추가
            if (current.left != null) {
                queue.offer(current.left);
            }

            // 오른쪽 자식이 있으면 큐에 추가
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
    }

    public static void main(String[] args) {
        // 간단한 이진 트리 생성
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // BFS 수행
        Tree tree = new Tree();
        tree.bfs(root);
    }
}

• 시작 노드(root)를 기준으로, 좌/우측의 자식 노드(= 인접 노드)를 확인
• 좌/우측의 자식 노드가 존재한다면 순차적으로 방문하기 위해 Queue에 이를 저장
• while 반복문을 사용하여 Queue에 저장된 인접 노드를 순차적으로 방문
• Queue에 더 이상 방문할 인접 노드가 없을 때까지 반복

 

BFS를 적용하는 경우

최단 거리/경로를 계산할 때 사용

• 인접 노드를 우선적으로 탐색하기 떄문
• DFS는 목적지와 반대 방향을 탐색하더라도 끝까지 탐색을 수행 → 최단 거리를 보장할 수 없음
• BFS는 인접 노드를 순차적으로 탐색 → 목적지와 가까운 노드를 순차적으로 탐색을 수행

 

DFS, BFS 활용한 문제 유형 및 응용

• 그래프의 모든 정점을 방문하는 것이 중요한 문제 (DFS, BFS)
  • 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 어느 것을 사용하여도 상관없음
• 경로의 특징을 저장해둬야 하는 문제 (DFS)
  • 예) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 되는 경우 
  • 각각의 경로마다 특징을 저장해둬야 할 때는 DFS 사용
• 최단거리 구해야하는 문제 (BFS)
  • 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리
• 검색 대상 그래프가 정말 큰 경우 (DFS)
• 검색 대상 규모가 크지 않고, 검색 지점으로부터 원하는 대상이 별로 멀지 않는 경우 (BFS)

 

 

출처 및 참고 : 

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

[코딩테스트 대비] DFS, BFS 정리

DFS/BFS 개념 및 문제 접근 방법