깊이/너비 우선탐색 (DFS / BFS) 알고리즘 / Java 코드

[개요]

그래프 탐색 알고리즘.

그래프 : 여러 개체들이 연결되어 있는 자료구조

탐색 : 특정 개체를 찾기 위한 알고리즘 

 

대표적 문제 유형

1. 경로탐색 유형 (최단거리, 시간)

2. 네트워크 유형 (연결)

3. 조합 유형 (모든 조합 만들기)

 

DFS : 재귀함수로 구현하는 것이 일반적

BFS : 큐나 링크드 리스트를 사용하여 구현하는 것이 일반적

 

[DFS - 깊이 우선 탐색]

 

 

[BFS - 너비 우선 탐색]

 

 

 

[Java 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class DFS_BFS_Test {

  static class Node {
    int idx;
    Node leftNode, rightNode;
  
    public Node(int idx) {
      this.idx = idx;
    }
  }


  public static void main(String[] args) {

    
    Node root = new Node(0);
    root.leftNode = new Node(1);
    root.rightNode = new Node(2);

    root.leftNode.leftNode = new Node(3);
    root.leftNode.rightNode = new Node(4);

    root.rightNode.leftNode = new Node(5);
    root.rightNode.rightNode = new Node(6);

    System.out.print("DFS : ");
    DFS(root);
    System.out.println();
    System.out.print("BFS : ");
    BFS(root);
  }

  private static void DFS(Node root) {
    if (root == null) return;
    System.out.print(root.idx + " ");
    DFS(root.leftNode);
    DFS(root.rightNode);
  }

  private static void BFS(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    //BFS 탐색
    while (!queue.isEmpty()) {
      Node current = queue.poll();
      if (current != null) {
        System.out.print(current.idx + " ");
        queue.add(current.leftNode);
        queue.add(current.rightNode);
      }
    }
  }

}