[Algorithm] 탐색 - DFS와 BFS

DFS와 BFS란?

일단, 항상 공부하기전에 용어를 정리하는 습관을 기르고자 합니다.

DFS(Depth-First Search) : 깊이 우선 탐색

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

 

말그대로, 깊이 먼저 탐색하냐, 너비 먼저 탐색하냐 차이인거 같아요

그렇다면 뭘 탐색할까요?

그래프(Graph) 탐색 알고리즘 입니다.

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

 

DFS와 BFS는 대표적인 그래프 탐색 알고리즘 입니다.

---

DFS의 동작 원리

깊이 우선 탐색 답게 깊이를  우선적으로 탐색합니다.

수직적 탐색 이라고 생각하면 쉬울것 같네요

이렇게 수직 방향으로 탐색을 하게 됩니다.

 

Java를 통해 구현해볼까요??

import java.util.LinkedList;

public class DFS {

    private int vertices;   // 그래프의 정점(노드)의 수
    private LinkedList<Integer> adjList[]; // 각 노드의 인접한 노드들을 저장하는 리스트

    // 생성자: 그래프의 초기화
    DFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adjList[i] = new LinkedList();
    }

    // 노드를 인접 리스트에 추가하는 함수
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // DFS의 핵심이 되는 재귀 함수
    // v: 현재 탐색 중인 노드, visited: 각 노드의 방문 여부를 저장하는 배열
    void DFSUtil(int v, boolean visited[]) {
        // 현재 노드를 방문한 것으로 표시하고 출력
        visited[v] = true;
        System.out.print(v + " ");

        // 인접한 모든 노드들에 대한 탐색
        for (Integer neighbor : adjList[v]) {
            if (!visited[neighbor]) // 만약 방문하지 않은 노드라면
                DFSUtil(neighbor, visited); // 재귀적으로 탐색
        }
    }

    // 주어진 노드에서 시작하여 DFS를 실행하는 함수
    void traverse(int v) {
        // 모든 노드에 대한 방문 여부를 저장하는 배열 초기화
        boolean visited[] = new boolean[vertices];

        DFSUtil(v, visited); // DFS 시작
    }

    public static void main(String args[]) {
        DFS g = new DFS(4); // 4개의 노드를 가진 그래프 생성

        // 그래프의 엣지 설정
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("DFS 시작 노드(2)에서의 탐색");

        g.traverse(2); // 노드 2에서 시작하는 DFS
    }
}

---

BFS의 동작 원리

너비 우선 탐색 답게 깊이를  우선적으로 탐색합니다.

수평적 탐색 이라고 생각하면 쉬울것 같네요

이렇게 수직 방향으로 탐색을 하게 됩니다.

Java를 통해 구현해볼까요??

import java.util.LinkedList;

public class BFS {

    private int vertices;   // 그래프의 정점(노드)의 수
    private LinkedList<Integer> adjList[]; // 각 노드의 인접한 노드들을 저장하는 리스트

    // 생성자: 그래프의 초기화
    BFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList<>();
    }

    // 노드를 인접 리스트에 추가하는 함수
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // BFS의 핵심 로직이 들어가는 함수
    void bfsUtil(int s, boolean visited[], LinkedList<Integer> queue) {
        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();  // 큐에서 노드를 꺼냄
            System.out.print(s + " ");

            // 인접한 모든 노드들에 대한 탐색
            for (Integer neighbor : adjList[s]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    // 주어진 노드에서 시작하여 BFS를 실행하는 함수
    void traverse(int s) {
        // 모든 노드에 대한 방문 여부를 저장하는 배열 초기화
        boolean visited[] = new boolean[vertices];
        LinkedList<Integer> queue = new LinkedList<>();

        bfsUtil(s, visited, queue);
    }

    public static void main(String args[]) {
        BFS g = new BFS(4); // 4개의 노드를 가진 그래프 생성

        // 그래프의 엣지 설정
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("BFS 시작 노드(2)에서의 탐색:");

        g.traverse(2); // 노드 2에서 시작하는 BFS
    }
}

---

대충 bfs와 dfs의 이론에 대해서 살펴보았습니다.

실제 코딩테스트 문제를 풀때는 이론만 안다고해서 풀 수 있는 것은 아니니 꼭! 코딩 테스트에 적용해서 풀어보면 좋을거 같습니다.