[JAVA] DFS , BFS

DFS( Depth-First Search ), BFS( Breadth-First Search )

---

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

• 시작 정점을 방문한 후 하나의 인접 정점을 따라 계속 방문.
  더 이상 방문할 정점이 없으면 되돌아와 다른 정점을 탐색함.
• 재귀 함수나 스택으로 구현 가능

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

스택의 LIFO(Last In Frist Out)를 고려해서 스택에 담기는 노드의 순서는 다음과 같다.

EMPTY

1

8,7,2

8,7,6,3

8,7,6,5,4

8,7,6,5

8,7,6

8,7

8

12,9

12,11,10

12,11

12

EMPTY

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

• 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문
• Queue 사용 (LinkedList로 구현)

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

큐의 FIFO(Frist In Frist OUT)를 고려해서 큐에 담기는 노드의 순서는 다음과 같다.

EMPTY

1

2,3,4

3,4,5,6

4,5,6

5,6,7,8

6,7,8,9,10

7,8,9,10

8,9,10,11,12

9,10,11,12

10,11,12

11,12

12

EMPTY

 

 

DFS와 BFS를 어느 상황에서 써야 할까?

 

DFS

특정 조건을 만족하는 모든 경로 탐색 (ex. 미로 탐색, 퍼즐) - 경로 찾기 문제

조합, 순열, 경우의 수 찾기 (ex. N-Queen, 완전 탐색) - 백트래킹 문제

전위, 중위, 후위 순회 등 트리 기반 탐색 - 트리 순회

 

BFS

모든 간선의 비용이 같을 때 최단 경로 찾기 (ex. 미로의 최소 이동 횟수) - 최단 거리 문제

그래프/트리의 같은 레벨(깊이) 노드 순차 처리 (ex. 너비 순 트리 탐색) - 레벨(깊이) 탐색

최소 시간, 최소 연산 횟수 등 (ex. 숫자 변환 최소 연산) - 최소 횟수/단계 문제

 

트리의 끝까지 탐색 +@전역 -> DFS

단계 별로 탐색 + 최소 -> BFS

---

관련 문제

백준 DFS+BFS 필수 문제

https://www.acmicpc.net/workbook/view/1983

---

 

1. DFS (Depth-First Search, 깊이 우선 탐색) 

인접 리스트 형태로 주어진 Graph 탐색

 

재귀로 구현

void dfsRecursive(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;                      // 현재 노드 방문 표시
    System.out.print(node + " ");              // 방문 노드 출력

    for (int next : graph.get(node)) {         // 인접 노드 탐색
        if (!visited[next]) {
            dfsRecursive(next, visited, graph); // 아직 방문 안 했으면 재귀 호출
        }
    }
}

 

 

스택으로 구현

void dfsWithStack(int start, boolean[] visited, List<List<Integer>> graph) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);                         // 시작 노드를 스택에 push

    while (!stack.isEmpty()) {
        int node = stack.pop();                // 스택에서 꺼냄

        if (!visited[node]) {
            visited[node] = true;              // 방문 처리
            System.out.print(node + " ");      // 방문 노드 출력

            List<Integer> neighbors = graph.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int next = neighbors.get(i);
                if (!visited[next]) {
                    stack.push(next);          // 인접 노드 스택에 push
                }
            }
        }
    }
}

 

위의 코드는 DFS를 통한 그래프 탐색만을 진행한다.
문제의 조건에 맞게 특정 값을 감지 or 특정 조건을 만족하면 값을 저장(배열에 저장,리스트에 저장,출력 문자열에 저장..) 가능

 

visited 배열을 쓰는 이유 ? -> 중복 방문을 방지

 

 

---

2. BFS (Breadth-First Search, 너비 우선 탐색)

큐로 구현

void bfs(int start, boolean[] visited, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

• 시작 노드를 큐에 넣고,
• 큐에서 꺼낸 노드의 인접 노드들을 다시 큐에 넣는 구조
• visited는 큐에 넣을 때 true 처리해서 중복 방지
• 그래프를 레벨 순서대로 탐색함 (너비 우선)

위의 코드는 BFS를 통한 그래프 탐색만을 진행한다.
문제의 조건에 맞게 특정 값을 감지 or 특정 조건을 만족하면 값을 저장(배열에 저장,리스트에 저장,출력 문자열에 저장..) 가능

 

visited 배열을 쓰는 이유 ? -> 중복 방문을 방지

---