[CS] DFS와 BFS

 

오늘의(라고 하지만 2달만에 쓰는)

알고리즘 주제는 바로

 

BFS와 DFS

 

이유는 모르겠지만 가장 어렵게 느껴지고,

항상 마스터하지 못한채 포기한 개념이었던 거 같은데...

이제는 더이상 물러날 곳이 없다

 

 

 우선 쉽게 어떤 느낌인지 파악해보자면 미로를 생각하면 된다.

그런데 이제 내가 이 미로 안에 들어가 있고, 출구와 전체적인 지도도 모를 때

이 미로를 푸는 방법은 두 가지다

 

1. 무작정 한 길로 쭉 가다가 막히면 다시 되돌아오기 => DFS!

2. 갈림길이 나오면 갈 수 있는 모든 곳을 다 훑어보고 다음 단계로 넘어가기 => BFS!

 

이 느낌을 가지고 DFS와 BFS를 좀 더 알아보자.

 

 

---

 

🗺️ DFS 

깊이 우선 탐색, Depth-First-Search

 

원문 그대로 'Depth = 깊이'를 우선적으로 탐색하는 알고리즘이다.

경로를 따라서 가능한 깊숙이 들어가서 탐색하고,

더 이상 갈 곳이 없으면 가장 최근에 방문했던 분기로 돌아가 다른 방향을 탐색한다.

 

 

 

하나씩 쌓이면서, 가장 최근에 방문한 노드를 먼저 깊게 들어가니까 > LIFO!

Last In Firsts Out 구조를 활용하는 스택을 활용하여 구현할 수 있다.

동시에 당연히 재귀호출을 사용해서도 구현할 수 있다

(느낌이 안오면 외우면 됨)

 

 

 

1. DFS - 스택으로 구현하기

 

일반적으로는 재귀호출을 사용하나, 재귀호출을 사용하지 않고 스택을 이용해서도 구현할 수 있다

public static void dfsStack(int startNode, List<List<Integer>> graph, boolean[] visited) {
    Stack<Integer> stack = new Stack<>(); // 스택 생성

	// 시작 노드 추가 및 방문 처리
    stack.push(startNode); 
    visited[startNode] = true; 
    
    // 스택이 비어있지 않은 동안 반복
    // 맨 위 노드를 확인하고 > 방문하지 않은 노드라면 탐색 > 방문 처리 > 다음 깊이
    while (!stack.isEmpty()) {
        int currentNode = stack.peek(); 
        boolean foundUnvisitedNeighbor = false; 

        for (int neighbor : graph.get(currentNode)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true; 
                stack.push(neighbor); 
                foundUnvisitedNeighbor = true; 
                break;
            }
        }

        // 현재 노드에서 더 이상 방문할 인접 노드가 없으면 (백트래킹) > 노드 제거
        if (!foundUnvisitedNeighbor) {
            stack.pop(); 
        }
    }
}

 

 

 

2. DFS - 재귀 호출을 이용

가장 일반적인 방식!

깊이 탐색을 반복하는 재귀를 이용해서 DFS를 구현한다.

 

public static void dfsRecursive(int node, List<List<Integer>> graph, boolean[] visited) {
    // 현재 노드를 방문 처리
    visited[node] = true;
    
    // 노드와 연결된 모든 인접 노드 탐색 > 아직 방문하지 않은 노드라면 > 해당 노드로 재귀 호출
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfsRecursive(neighbor, graph, visited);
        }
    }
}

 

 

 

주의할 점은!

DFS로 탐색한 경로는 최단 경로를 보장하지 않는다.

동시에 깊이가 긴 그래프의 경우 오버플로우가 발생할 수 있다.

 

다만 메모리 사용이 일반적으로 BFS보다 적다.

 

 

DFS는 따라서

 

1. 특정 깊이에 있는 노드를 찾을 때 

2. 가능한 모든 경로를 탐색해야 될 때

3. 사이클(순환되는 경로)의 존재를 파악할 때 

 

BFS보다 유리하다

 

 

---

 

🗺️ BFS 

너비 우선 탐색, Breadth-Frist Search

 

BFS는 앞서 설명한 미로에서 갈림길을 만나면 모든 곳을 다 가보는,

즉 현재 깊이의 모든 노드를 먼저 탐색 후에 다음 깊이로 넘어가는 방식이다.

 

 

시작 노드에서 가까운 노드를 먼저 탐색하므로

점점 범위를 넓혀가며 탐색한다

 

DFS가 깊게 들어갔다 넓게 가는 느낌이라면,

BFS는 넓게 먼저 다 보고 가는 느낌!

 

 

먼저 들어온걸 먼저 다 보기 때문에 (0 - 1 - 2)

First In First Out > 큐를 사용하여 구현한다!

 

 

 

public static void bfs(int startNode, List<List<Integer>> graph, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();

    queue.add(startNode); 
    visited[startNode] = true; 

    // 큐에 노드를 넣고(현재 탐색할 노드) > 노드와 연결된 모든 노드를 탐색 > 방문
    while (!queue.isEmpty()) {
        int currentNode = queue.poll(); 

        for (int neighbor : graph.get(currentNode)) {

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

 

 

BFS의 경우 가중치가 없는(간선에 특정한 값) 경우 최단 경로를 반드시 보장한다

 

따라서 최단 시간이나, 최소 이동 횟수 등의 알고리즘에서 유용하게 사용된다.

 

 

---

 

 

두 알고리즘을 언제 쓰나요?

하고 비교해보면!

 

DFS	BFS
경로의 존재만 확인하면 되는 경우(연결만 따질 때) 메모리가 제한적일 때 가능한 모든 경로를 탐색해야될 때(백트래킹)	최단 경로를 구해야 할 때 가까운 노드부터 처리해야 할  때 시작점이 여러개 + 동시에 탐색할 때

 

 

 

 

DFS와 BFS를 간단하게 비교해볼 수 있는

인터랙티브 페이지를 만들었다!

 

눌러보면서 비교해보고 싶으면 아래 페이지를 확인해보자

 

 

 

🔗 https://bit.ly/dfs-with-bfs

이미지를 누르면 창으로 이동합니다

 

 

 

---

 

마지막으로 단계별로 풀어볼 수 있는 DFS와 BFS 문제!

를 추천합니다

(나도 얼른 풀어야지..)

 

 

	백준	리트코드	프로그래머
입문	1926 그림 2178 미로 탐색	733 Flood Fill 200 Number of Islands 695 Max Area of Island	43165 타겟 넘버 1844 게임 맵 최단거리
중급	24479 알고리즘 수업 1012 유기농 배추	994 Rotting Oranges 797 All Paths From Source to Target	60058 괄호 변환 67259 경주로 건설
고급	9466 텀 프로젝트 13913 숨바꼭질 4	847 Shortest Path Visiting All Nodes 329 Longest Increasing Path in Matrix	118669 등산코스 정하기 92343 양과 늑대

 

 

 

 

---

 

 

 

DFS와 BFS를 마스터하는 그날까지..

아자아자

 

 

 

 

*오류나 질문, 수정 사항 등은 댓글로 알려주세요