[JAVA]DFS와 BFS

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

가능한 한 깊이 들어가며 탐색한 뒤, 더 이상 갈 수 없을 때 되돌아오는 방식. 스택 구조를 기반으로 하며, 재귀 또는 명시적 스택 이용한다. JAVA는 구조적으로 JVM에서 각 쓰레드별로 고정된 크기의 콜 스택을 주며, 이 크기가 매우 작다. 따라서 많은 재귀 depth를 가지지 못한다. 그러므로 명시적으로 스택 자료구조를 사용한다.

출처 : https://developer-mac.tistory.com/64

출처 : https://velog.io/@kyeun95/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BFSDFS

DFS 구현 시 유의사항

1. 재귀 깊이를 구현 언어가 감당할 수 있는지 확인(JAVA는 위험이 큼).

2. 방문 체크(visited) 필요 - 무한 탐색을 막기 위함(트리가 아닌, 사이클의 경우).

 

 

 

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

시작 정점에서 가까운 정점부터 차례로 탐색, 모든 인접 노드를 탐색한 후 다음 노드를 방문. 큐 구조를 사용.

출처 : https://developer-mac.tistory.com/64

출처 : https://velog.io/@kyeun95/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BFSDFS

 

BFS 구현 시 유의사항

1. 방문 체크(visited) 타이밍 : 큐에 넣기 전에 visited 체크를 해야 함. 큐에서 꺼낸 뒤 visited 체크를 하게 되면, 중복 탐색이 발생할 수 있음.

 

 

 

JAVA를 활용한 DFS/BFS 구현

Stack과 Queue 자료형이 있지만, 좀 더 좋은 ArrayDeque를 사용하면 Stack과 Queue 둘 다 구현이 가능해서 편하다.

Java 6 (JDK 1.6) 버전부터 사용할 수 있어서, 왠만하면 사용 가능할 것이라고 생각한다.

 

아래 코드를 보면 알겠지만, 두 탐색 방식의 코드 구조는 거의 같다고 봐도 무방하다. 따라서 구현에 사용하는 자료형에 따라 DFS인지, BFS인지 정해진다고 보면 된다.

DFS

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
        int N = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(1).add(2); graph.get(2).add(1);
        graph.get(1).add(3); graph.get(3).add(1);
        graph.get(2).add(4); graph.get(4).add(2);
        graph.get(3).add(5); graph.get(5).add(3);

        boolean[] visited = new boolean[N + 1];
        Arrays.fill(visited,false);
        
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        stack.push(1);
        visited[1] = true;
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.println("node : "+node+ "방문");
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    stack.push(next);
                    visited[next] = true;
                }
            }
        }

    }
}

BFS

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
        int N = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(1).add(2); graph.get(2).add(1);
        graph.get(1).add(3); graph.get(3).add(1);
        graph.get(2).add(4); graph.get(4).add(2);
        graph.get(3).add(5); graph.get(5).add(3);

        boolean[] visited = new boolean[N + 1];
        Arrays.fill(visited,false);
        
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        queue.offer(1);
        visited[1] = true;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.println("node : "+node+ "방문");
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true; // 주의해야 하는 부분. 같은 노드가 큐에 여러 번 들어가는 것을 방지하기 위해, 큐에 넣는 순간 true.
                }
            }
        }

    }
}

 

DFS와 BFS 문제풀이들

https://chabin37.tistory.com/103

[JAVA] 백준 2667 단지번호붙이기

https://chabin37.tistory.com/104

[JAVA] 백준 16946 벽 부수고 이동하기 4

https://chabin37.tistory.com/122

[JAVA] 백준 1167 트리의 지름

https://chabin37.tistory.com/123

[JAVA] 백준 1967 트리의 지름

https://chabin37.tistory.com/125

[JAVA] 백준 1135 뉴스 전하기

https://chabin37.tistory.com/150

[JAVA] 백준 7576 토마토

 

https://chabin37.tistory.com/158

[JAVA] 백준 13549 숨바꼭질3