BFS/DFS란?

오늘은 기본적인 알고리즘인 DFS와 BFS에 대해서 알아보겠습니다.

 

BFS란?

BFS란 Breadth-First Search의 약자로 번역하면 너비 우선 탐색입니다. 이는 트리 구조에서 많이 사용되곤 합니다.

어떤 대상 노드로부터 가장 가깝게 연결된 노드들부터 탐색하며 순차적으로 트리의 전체를 순회하는 구조를 일컫습니다.

(트리의 용어가 어색한 분들은, 아래의 그림을 보고 우선은 단순하게 이런 식으로 생긴 놈이구나 라고 생각하시면 좋을 것 같습니다.)

 

아래의 자료를 보면 금방 이해하실 수 있습니다.

루트 노드인 1로부터 가장 가깝게 연결된 3개를 순서대로 순회합니다. 그 후, 2와 연결된 노드를 방문하고, 최종적으로는 트리의 모든 노드를 방문하는 방법입니다.

 

그럼 BFS의 소스 코드를 살펴보겠습니다. 제가 주로 사용하는 방법은 큐를 이용하여 구현하는 방법입니다. 간단한 과정을 설명하자면 아래와 같습니다.

- 가장 먼저 루트 노드를 큐에 넣습니다.

1. 큐에서 노드 하나를 pop합니다.

2. pop한 노드에 연결되어 있는 모든 노드들을 Iterator를 이용해서 순환하며 큐에 삽입해줍니다.

    - 삽입하기 전, 이 노드가 기존에 큐에 삽입되었던 노드인지를 확인하여 기존에 삽입되었던 기록이 있다면 삽입하지 않습니다.

3. 모든 노드를 방문할 때까지 1-2를 반복해줍니다.

 

import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        Graph gp = new Graph(8);
        gp.addEdge(0, 1);
        gp.addEdge(0, 2);
        gp.addEdge(0, 3);
        gp.addEdge(1, 4);
        gp.addEdge(1, 5);
        gp.addEdge(3, 6);
        gp.addEdge(4, 7);
        gp.BFS(0); // 루트 노드를 인덱스 0번째 값으로 삼아라!
    }

}
class Graph{
    static LinkedList<Integer>[] obj;
    static boolean[] visited;

    Graph(int n){
        obj = new LinkedList[n];
        for (int i = 0; i < n; i++) obj[i] = new LinkedList<>();
        visited = new boolean[n];
    }

    void addEdge(int i, int j){
        obj[i].add(j);
    }

    void BFS(int n){
        visited[n] = true;
        LinkedList<Integer> q = new LinkedList<>();
        q.add(n);

        while(!q.isEmpty()){
            int s = q.poll();

            System.out.println(s);

            ListIterator<Integer> it = obj[s].listIterator();
            while (it.hasNext()) {
                int x = it.next();
                if(!visited[x]){
                    q.add(x);
                    visited[x] = true;
                }
            }
        }
    }

}

 

코드를 예시와 함께 다시 설명해보겠습니다.

 

아래와 같이 노드의 이름이 주어져있다고 가정해봅시다.

그럼 여기서 BFS로 구현했을 때, 어떤 순서대로 방문을 할까요??

코드를 돌려 결과를 확인해보면 1 2 3 4 5 6 7 8 순서대로 출력하게 됩니다!!

 

다시 한번 정리하면, BFS는 루트 노드로부터 가까운 노드부터 순차적으로 트리의 전체를 순환하는 방법을 의미합니다. BFS는 큐를 이용하여 구현할 수 있습니다.

 

---

 

DFS란?

Depth-Frist Search의 약자로, 해당 노드와 가장 먼저 연결되어있는 노드의 최단까지 탐색 후, 그 다음과정을 거치는 과정이라고 할 수 있습니다. BFS와는 조금 상반되는(?) 개념으로 이해해도 무방합니다.

 

BFS를 이해하셨다면, 충분히 이해하실 수 있는 내용일테니 바로 소스코드로 넘어가겠습니다. DFS는 BFS와 다르게 큐로 구현하지 않고, 재귀함수를 이용해 구현합니다.

import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        Graph gp = new Graph(8);
        gp.addEdge(0, 1);
        gp.addEdge(0, 2);
        gp.addEdge(0, 3);
        gp.addEdge(1, 4);
        gp.addEdge(1, 5);
        gp.addEdge(3, 6);
        gp.addEdge(4, 7);
        gp.DFS(0); // 루트 노드를 인덱스 0번째 값으로 삼아라!
    }

}
class Graph{
    boolean[] visited;
    static LinkedList<Integer>[] obj;

    Graph(int n){
        obj = new LinkedList[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) obj[i] = new LinkedList<>();
    }

    void addEdge(int i, int j){
        obj[i].add(j);
    }

    void DFS(int n){
        visited[n] = true;
        DFS(n, visited);
    }
    void DFS(int n, boolean[] visited){
        visited[n] = true;
        System.out.println(n);

        ListIterator<Integer> it = obj[n].listIterator();
        while (it.hasNext()) {
            int s = it.next();
            DFS(s, visited);
        }
    }
}

아까와 같이 위처럼 트리가 있다고 하면, 출력은 1 2 5 8 6 3 4 7 순서로 출력하게 됩니다.

---

마치며..

한 가지 이 알고리즘을 공부하고 문제를 풀어보면서 느낀 점은, 이 소스코드에 국한되지 말아야한다는 것입니다. 처음에 문제를 풀 때는 저 형식에서 벗어나면 안 되는 줄 알고 편협하게 문제에 접근하게 되는 단점이 있었는데, 어느정도 많은 문제들을 접하다 보니 요령도 생기게 되는 것 같습니다.

 

간혹, 알고리즘을 처음 접하면서 어떻게 코드를 적용할 지 막막할 때가 온다면, 초반에는 정답과 함께 알고리즘을 우선 익히시는 방법을 추천드립니다!!