JAVA 코딩테스트:: DFS, BFS는 어느 문제에서 풀어야 할까?

DFS (Depth-First Search)

깊이 우선 탐색 DFS는 그래프 탐색 알고리즘 중 하나로, 그래프의 모든 정점을 방문하는 방법 중 하나이다.

DFS는 가능한 깊이 있는 노드를 먼저 방문하는 방식으로 작동한다.

 

ex)

미로의 출구를 찾을 때, 가능한 깊숙히 들어간다.

여러 갈래의 길이면 한 방향으로 끝까지 가보고 막다른 길이면 돌아와서 다른 길을 간다.

시작 노드 : A

A -> B -> D

D -> B

B -> C -> E

즉, A -> B -> D -> C -> E

 

 

DFS 예시

import java.util.*;

public class DFSExample {
    static class Graph {
        private int V; // 정점의 수
        private LinkedList<Integer> adj[]; // 인접 리스트 

        // 생성자
        Graph(int v) {
            V = v;
            adj = new LinkedList[v];
            for (int i = 0; i < v; ++i)
                adj[i] = new LinkedList();
        }

        // 그래프에 간선 추가
        void addEdge(int v, int w) {
            adj[v].add(w);
        }

        // DFS에서 사용하는 함수
        void DFSUtil(int v, boolean visited[]) {
            // 현재 방문한 노드를 체크하고 출력
            visited[v] = true;
            System.out.print(v + " ");

            // 해당 정점에 인접한 모든 정점에 대해 반복
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n])
                    DFSUtil(n, visited);
            }
        }

        // DFS 함수
        void DFS(int v) {
            // 방문하지 않은 모든 정점 체크
            boolean visited[] = new boolean[V];

            // 재귀 도움 함수를 호출해서 DFS 순회 출력
            DFSUtil(v, visited);
        }

        public static void main(String args[]) {
            Graph g = new Graph(5);

            g.addEdge(0, 1);
            g.addEdge(0, 2);
            g.addEdge(1, 3);
            g.addEdge(2, 4);

            System.out.println("Following is Depth First Traversal " +
                               "(starting from vertex 0)");

            g.DFS(0); // 정점 0번 부터 DFS 시작
        }
    }
}

1. 그래프 클래스

- Graph 클래스에는 정점 수, 인접 리스트가 있음

- addEdge 메서느는 두 정점 간의 간선을 추가함

 

2. DFS 메서드

- DFSUtil은 재귀적으로 호출되어 깊이 우선 탐색 수행

- DFS 메서드는 모든 정점을 방문하지 않았다고 표시하고, DFSUtil 메서드 호출해서 탐색 시작

 

3. 메인 함수

- 그래프 정의, 간선 추가, 정점 0에서 DFS 시작

 

 

 

---

DFS, BFS의 적합한 문제 유형

---

📌 DFS, BFS 모두 적합한 유형

단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 어떤 것을 택해도 된다.

📌 DFS가 적합한 유형

검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많음)
경로의 특징을 저장해둬야 하는 문제
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제
BFS는 경로의 특징을 가지지 못함

📌 BFS가 적합한 유형

미로찾기 등 최단거리를 구해야 할 경우
DFS는 처음으로 발견되는 해답이 최단거리 라는 것 보장 X
반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.