DFS와 BFS 알고리즘 완벽 가이드!! [탐색 알고리즘의 기본부터 예제 코드까지] 포스팅 하나로

탐색 알고리즘은 그래프를 순회하거나 특정 조건을 만족하는 경로를 찾는 데 자주 사용된다.

 

특히 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 가장 기초적이면서도 중요한 탐색 기법으로, 많은 문제 해결의 기반이 된다.

 

이번 포스팅 에서는 DFS와 BFS의 개념, 작동 방식, 예제 코드, 그리고 두 알고리즘의 차이점으로 작성해보려 한다.

 

 

 

 

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

DFS란?

깊이 우선 탐색은 시작 노드에서 한 방향으로 깊게 들어가며 탐색을 진행하는 방식이다. 한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없을 때 다른 경로로 이동한다.

• 주요 특징:
  • 스택 자료구조(혹은 재귀 호출)를 사용한다.
  • 그래프의 경로가 깊은 곳까지 먼저 탐색된다.
  • 순환 구조나 무한 루프를 방지하기 위해 방문 처리가 필요하다.

DFS 동작 방식

1. 시작 노드를 방문 처리한다.
2. 현재 노드와 연결된 모든 노드 중 방문하지 않은 노드로 이동한다.
3. 더 이상 방문할 노드가 없으면 이전 노드로 돌아온다.

 

예제 코드

import java.util.*;

public class GraphTraversal {
    public static void DFS(int startNode, Map<Integer, List<Integer>> graph, boolean[] visited) {
        // 방문 처리
        visited[startNode] = true;
        System.out.print(startNode + " ");

        // 현재 노드와 연결된 노드 탐색
        List<Integer> neighbors = graph.getOrDefault(startNode, new ArrayList<>());
        Collections.sort(neighbors); // 정렬하여 순서 보장

        for (int neighbor : neighbors) {
            if (!visited[neighbor]) {
                DFS(neighbor, graph, visited);
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(5, 6));
        graph.put(3, Arrays.asList(7));
        graph.put(4, Arrays.asList());
        graph.put(5, Arrays.asList());
        graph.put(6, Arrays.asList());
        graph.put(7, Arrays.asList());

        boolean[] visited = new boolean[8];
        System.out.println("DFS 탐색 순서:");
        DFS(1, graph, visited);
    }
}

 

 

 

 

 

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

BFS란?

너비 우선 탐색은 시작 노드에서 가까운 노드부터 탐색을 진행하는 방식이다. 한 단계씩 너비를 확장하며 탐색이 진행된다.

• 주요 특징:
  • 큐 자료구조를 사용한다.
  • 노드가 같은 깊이에 있는 경우, 탐색 순서가 보장된다.
  • 경로 탐색이 짧은 경우에 유리하다.

BFS 동작 방식

1. 시작 노드를 방문 처리하고 큐에 삽입한다.
2. 큐에서 노드를 꺼낸 후, 해당 노드와 연결된 모든 노드 중 방문하지 않은 노드를 큐에 삽입한다.
3. 큐가 빌 때까지 반복한다.

예제 코드

import java.util.*;

public class GraphTraversal {
    public static void BFS(int startNode, Map<Integer, List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode); // 시작 노드를 큐에 삽입
        visited[startNode] = true;

        while (!queue.isEmpty()) {
            int currentNode = queue.poll(); // 큐에서 노드 꺼내기
            System.out.print(currentNode + " ");

            // 현재 노드와 연결된 노드 탐색
            List<Integer> neighbors = graph.getOrDefault(currentNode, new ArrayList<>());
            Collections.sort(neighbors); // 정렬하여 탐색 순서 보장

            for (int neighbor : neighbors) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true; // 방문 처리
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(5, 6));
        graph.put(3, Arrays.asList(7));
        graph.put(4, Arrays.asList());
        graph.put(5, Arrays.asList());
        graph.put(6, Arrays.asList());
        graph.put(7, Arrays.asList());

        boolean[] visited = new boolean[8];
        System.out.println("BFS 탐색 순서:");
        BFS(1, graph, visited);
    }
}

 

 

 

 

DFS와 BFS의 차이점

구분	DFS	BFS
탐색 순서	깊이 우선	너비 우선
사용 자료구조	스택 (혹은 재귀 호출)	큐
경로 탐색	전체 경로 탐색 시 유리	최단 경로 탐색 시 유리
구현 난이도	재귀를 사용하는 경우 간단	큐 사용으로 직관적
방문 순서 보장	보장되지 않을 수 있음	보장됨

 

 

언제 DFS와 BFS를 사용할까?

1. DFS를 사용하는 경우
   • 그래프 전체를 탐색하거나 특정 조건에 맞는 경로를 찾고 싶을 때.
   • 순환 구조를 다룰 때 (예: 사이클 탐지).
2. BFS를 사용하는 경우
   • 최단 경로를 찾고 싶을 때.
   • 계층적 구조를 탐색할 때 (예: 소셜 네트워크 분석).

 

DFS와 BFS는 그래프 탐색의 기초이자, 다양한 문제 해결에 활용되는 중요한 알고리즘이다.

 

각 알고리즘의 특징과 장단점을 이해하고 상황에 맞게 선택하는 것이 중요하다.

위의 설명과 코드를 바탕으로 백준 등에서 직접 구현해 보는것을 추천한다!