[알고리즘/Java/Kotlin]BFS vs DFS

 

BFS와 DFS는 그래프 탐색 알고리즘 중 대표적인 두 가지 방법입니다.

프로그래머스 문제를 풀다보면 해답으로 꼭 있는 것이 BFS 혹은 DFS입니다.

그런 문제를 풀 때마다 나에게 익숙한 DFS를 사용하여풀었는데,  정확한 개념 정리가 필요할 것 같아 정리해보았습니다. 

 

* 아래 코드 설명

- Node는 그래프의 노드를 나타내는 클래스

   - 각 노드는 그래프 상에서 연결된 다른 노드들의 리스트를 가지고 있음

- start는 탐색을 시작할 노드를 나타내는 변수

- visited는 이미 방문한 노드들의 집합을 나타내는 변수

BFS (너비 우선 탐색)

BFS(너비 우선 탐색)는 시작 정점으로부터 가까운 정점을 먼저 탐색하는 방법입니다.

즉, 현재 정점에서 인접한 정점을 큐에 추가하고, 큐에서 하나씩 뽑아 탐색을 진행합니다.

이때, 방문한 정점은 다시 큐에 넣지 않습니다.

그래프의 최단 경로를 찾는 문제나 모든 정점을 탐색하는 문제에 사용됩니다.

Kotlin

fun bfs(start: Node) {
    val queue = LinkedList<Node>()
    val visited = mutableSetOf<Node>()
    queue.offer(start)
    visited.add(start)
    while (queue.isNotEmpty()) {
        val node = queue.poll()
        // node 처리
        for (next in node.neighbors) {
            if (next !in visited) {
                queue.offer(next)
                visited.add(next)
            }
        }
    }
}

Java

void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        // node 처리
        for (Node next : node.neighbors) {
            if (!visited.contains(next)) {
                queue.offer(next);
                visited.add(next);
            }
        }
    }
}

 

DFS(깊이 우선 탐색)

DFS(깊이 우선 탐색)는 시작 정점에서부터 깊게 탐색하는 방법입니다.

즉, 현재 정점에서 인접한 정점을 재귀적으로 탐색합니다.

이때, 방문한 정점은 스택(또는 재귀함수 호출 스택)에 넣습니다.

그래프의 순환 구조를 찾는 문제나 모든 정점을 탐색하는 문제에 사용됩니다.

Kotlin

fun dfs(node: Node, visited: MutableSet<Node>) {
    visited.add(node)
    // node 처리
    for (next in node.neighbors) {
        if (next !in visited) {
            dfs(next, visited)
        }
    }
}

Java

void dfs(Node node, Set<Node> visited) {
    visited.add(node);
    // node 처리
    for (Node next : node.neighbors) {
        if (!visited.contains(next)) {
            dfs(next, visited);
        }
    }
}

 

BFS vs DFS

BFS	DFS
최단 경로 보장 O	최단 경로 보장 X
구현 간단	구현 복잡
공간 복잡도 ↑	적은 메모리