Java 알고리즘 DFS와 BFS 완벽 정리

오늘은 Java 알고리즘에서 빼먹을 수 없는 DFS와 BFS에 대해 알아보려고 합니다. DFS는 Depth First Search의 약자로 깊이 우선 탐색을 말하고, BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말합니다. 이 둘은 그래프 자료구조에서 완전 탐색을 수행하는 탐색 기법입니다😊

 

DFS vs BFS

 

개요

앞서 말씀드린 그래프를 탐색하기 위한 대표적인 알고리즘 DFS, BFS를 이해하기 위해서는 스택(Stack), 큐(Queue), 재귀(Recursive)를 먼저 알아야 합니다. 스택과 재귀를 모르신다면 링크를 클릭해서 선수 학습을 해주세요😅

 

재귀 함수와 스택 프레임

 

큐(Queue)📙

큐는 스택과 반대로 선입선출(First in First out) 개념으로 입구와 출구가 모두 뚫려 있는 터널로 생각하시면 됩니다. 

 

public calss Main{
    public static void main(String[] args){
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);   
        q.offer(2);   
        q.offer(3);      
        q.poll(); // 1 출력
        q.offer(4);    
        q.poll(); // 2 출력
    }
}

 

전역 클래스 Node📗

DFS와 BFS 모두 사용할 Node 클래스를 미리 선언하였습니다. 노드는 그래프의 각각의 지점이라고 생각하시면 됩니다.

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

그래프

 

A번 노드는 lt에 해당하는 B번 노드, rt에 해당하는 C번 노드가 있습니다. 마찬가지로 B번 노드에는 lt에 해당하는 D번 노드, rt에 해당하는 E번 노드가 있습니다. 이런 식으로 Node 클래스는 val(ex: A)와 lt, rt 값으로 사용될 예정입니다😄

 

DFS📒

DFS

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닙니다. 위에 그림처럼 0에서 1로 1에서 3으로 갔을 때 더 이상 갈 곳이 없으면 백 트랙킹(BackTracking)을 해서 다시 1로 가게 됩니다. 이후에 방문하지 않은 4를 방문하게 되는 형태입니다.

 

흔히 미로를 예시로 많이 드는데요. 미로를 탐색할 때, 해당 분기에서 갈 수 있을때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서(백 트랙킹) 다른 방향으로 다시 탐색을 진행하는 방식입니다.

 

DFS는 대게 스택(Stack)을 사용하고 모든 노드를 방문하고자 할 때 사용합니다. BFS보다 더 간단하게 구현되지만 검색 속도 자체는 BFS에 비해 느립니다. 한번 코드로 구현해볼까요?

 

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);
    }
}

 

첫 번째로는 위의 사진처럼 트리 형식으로 노드를 구성합니다. 이후에 DFS() 함수를 실행시킵니다. 인자값으로 tree.root를 넣었는데 첫 번째 노드 값 0이 들어가겠죠?

 

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

출력 결과

위 그림처럼 왼쪽부터 순차적으로 깊이 우선 탐색이 실행된 것을 확인할 수 있습니다. 코드상으로 어떻게 실행이 된 걸까요? 처음에 DFS(tree.root) 함수를 호출시켰을 뿐입니다. 즉 DFS 인자값으로 0이 처음 들어옵니다.

 

0은 null이 아니기 때문에 else문을 타게 되고 0을 출력한 후에 DFS(root.lt)를 호출합니다. 즉 0의 왼쪽 노드인 1을 호출하는 것이죠. 그러면 DFS(root.rt)는 스택에 쌓이고 DFS(root.lt)를 실행합니다.

 

DFS(root.lt)가 실행하면 인자값으로 1이 넘어옵니다. 마찬가지로 1은 null이 아니기 때문에 else문을 타게 됩니다. 1을 출력한 후에 DFS(root.lt)를 실행합니다. 이번에도 똑같이 DFS(root.rt)는 스택에 쌓이게 됩니다.

 

stack

 

DFS(1의 root.lt = 3)이 실행되고 현재까지 System.out.print()로 콘솔에 출력한 것은 0 1 3 입니다. 그다음 수행할 것은 3의 lt가 들어가게 되겠죠? 하지만 tree에 3의 lt 값은 없습니다. 즉 null 이기 때문에 return 됩니다. 이 부분이 이전에 언급한 백 트랙킹(BackTracking) 입니다. 

 

그러면 3에서 백 트랙킹을 해서 1로 다시 넘어오고 스택에 쌓인 DFS(1의 root.rt = 4)가 수행됩니다. 이런 로직이 계속해서 반복하여 모든 노드를 탐색하게 됩니다.

 

📌 DFS는 if~else문 사용😊

 

출처 : Code States

 

 

BFS📘

BFS

 

BFS는 재귀적으로 동작하지 않고 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐(Queue)를 사용합니다. 즉, 선입선출 원칙으로 탐색합니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에 대게 두 노드 사이의 최단 경로를 찾을 때 주로 사용합니다. 

 

tree는 DFS와 동일하게 구성하였습니다.

 

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) {
            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();
    }
}

출력 결과

위 그림처럼 넓이 우선 탐색이 실행된 것을 확인할 수 있습니다. 코드상으로는 어떻게 실행된 걸까요? 

 

처음은 DFS와 똑같이 인자값으로 0이 들어옵니다. 그리고 Queue에 0을 넣게 됩니다. L은 레벨을 뜻하고 초기 값으로는 0으로 세팅해 주었습니다.(레벨은 편의상 넣은 것입니다)

 

while문은 Queue가 비어있을 때까지 반복해서 돌아갑니다. 현재 Queue에는 0 하나만 들어가 있기 때문에 길이 len은 1입니다. 반복문을 돌면서 Queue에서 첫 번째 값을 꺼내오고(0이 꺼내지겠죠?) 그 값을 출력한 후에 lt와 rt값이 있다면 Queue에 넣어줍니다.

 

이제는 Queue에 2개의 값(1,2)이 들어있습니다. 반복문을 Queue의 길이인 2만큼 돌면서 하나씩 꺼내서 값을 출력해주고 이번에도 lt와 rt값이 있다면 Queue에 넣어줍니다. 

 

쉽게 말해서 0일 때 1,2를 큐에 넣어주고, 1일 때 3,4를 큐에 넣어주고, 2일 때 5,6을 큐에 넣어주는 형식입니다. 그리고 들어간 순서대로 꺼내져 나오는 것이죠😄

출처 : Code States

 

📌 BFS는 while문 사용😊

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 DFS와 BFS에 대해 알아보았습니다. 탐색의 기초 알고리즘이기 때문에 꼭 숙지하시고 다음 활용 편에서 봬요😄