정의

간단하게 예를 들어서 설명해보면,

• DFS: 한 드라마를 한번에 몰아본다.
• BFS: 여러 드라마를 동시에 챙겨본다.

DFS

• 최대한 깊이(depth) 탐색한 후, 더 이상 깊이 갈 수 없다면 옆으로 이동하여 탐색
• 재귀함수나 Stack으로 구현
• 모든 노드를 방문하는 경우에는 DFS를 이용한다.
• DFS가 BFS보다 더 간단하다.
• 검색 속도 자체는 BFS보다 느리다.
• ex) 미로찾기를 할 때, 최대한 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 다시 갈림길으로 돌아가서 다른 방향부터 다시 탐색을 시작하는 것

BFS

• 인접한 노드들을 먼저 넓게(breadth) 탐색하고 아래로 이동하여 탐색
• Queue나 LinkedList로 구현
• 최단 경로를 구할 때 BFS를 사용한다.

문제 유형

1) 그래프의 모든 정점을 방문해야하는 문제 -> 두 방법 모두 가능!

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

2) 경로의 특징을 저장해둬야 하는 문제 -> DFS

각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다! (BFS는 경로의 특징을 가지지 못하기 때문에)

3) 최단거리 문제 -> BFS

DFS로 최단 경로를 검색할 경우, 처음으로 발견되는 해답이 최단거리가 아닐 수 있기 때문에

구현

DFS

public class DFS {
    //각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
    public static boolean[] visited = {false, false, false ,false ,false ,false ,false ,false, false};
    // 각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
    public static int[][] graph = {{},
            {2, 3, 8},
            {1, 7},
            {1, 4, 5},
            {3, 5},
            {3, 4},
            {7},
            {2, 6, 8},
            {1, 7}};

    public static void main(String[] args){
        int start = 1; // 시작 노드
        dfs(start);
    }

    /*
     * dfs 알고리즘을 수행하는 함수
     * @param v 탐색할 노드
     */
    public static void dfs(int v){
        // 현재 노드 방문 처리
        visited[v] = true;
        // 방문 노드 출력
        System.out.print(v + "");

        // 인접 노드 탐색
        for (int i : graph[v]){
            // 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
            if (visited[i]==false){
                dfs(i);
            }
        }
    }
}

BFS

public class BFS {
    public static void main(String[] args){
        //각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
        boolean[] visited = {false, false, false ,false ,false ,false ,false ,false, false};
        //각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
        int[][] graph = {{},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};
        // 시작 노드
        int start = 1;

        // 큐 구현
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        // 현재 노드를 방문 처리
        visited[start] = true;

        // 큐가 빌때까지 반복
        while(!queue.isEmpty()){
            // 큐에서 하나의 원소를 뽑아 출력
            int v = queue.poll();
            System.out.println(v + " ");

            // 인접한 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
            for (int i : graph[v]){
                if (visited[i] == false){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

[참고]
https://devuna.tistory.com/32
https://velog.io/@cha-suyeon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EA%B3%BC-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS
https://bbangson.tistory.com/42
https://scshim.tistory.com/241