DFS vs BFS

목차

---

🔔 깊이 우선 탐색 (DFS)

• 재귀 함수, 스택 → LIFO
• 시간 복잡도 : O(V+E)

 

핵심 이론

- 인접 리스트 & 방문 배열

- 재귀 + 백트래킹

 

문제 유형

- 단절점 찾기

- 단절선 찾기

- 사이클 찾기

- 위상 정렬

- 연결 요소 개수 / 재귀 깊이 (= DFS 수행 횟수)

- 순열 / 조합

 

DFS 구현 메소드 - 재귀 함수 사용

public static void DFS(int node) {
    // 1) 종료 조건 : 현재 노드가 이미 방문한 노드인 경우
    if(visited[node]) return;

    // 현재 연결 노드 中 방문하지 않은 노드인 경우
    visited[node] = true;

    // 2) 재귀
    for(int i : A[i]) {
        if(!visited[i]) {
            DFS(i);
        }
    }
}

 

---

🔔 너비 우선 탐색 (BFS)

• 큐 → FIFO
• 시간 복잡도 : O(V+E)

 

핵심 이론

- 인접 리스트 & 방문 배열

- 큐에서 노드 꺼내고, 인접 노드를 큐에 삽입하면서 방문 배열 체크

- 배열에 값을 저장하며 해결 가능한 경우 多

 

문제 유형

- 최단 경로 탐색 (최단 경로 저장할 int형 배열 필요)

 

BFS 구현 메소드 - 큐 사용

public static void BFS(int node) {
    visited[node] = true;
    
    Queue<Integer> q = new LinkedList<>();
    q.add(node);

    while(!q.isEmpty()) {
        int now_node = q.poll();

        for(int i : A[now_node]) {
            if(!visited[i]) {
                visited[i] = true;
                q.add(i);
            }
        }
    }
}

 

 

---

(참고)

▷ 대표 예제

[백준/JAVA] 1260번: DFS와 BFS

 

 

▷ 인접 행렬 사용 방법

그래프 표현 (인접 리스트 / 인접 행렬)

[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)

[Java] 그래프를 탐색하기 위한 인접 행렬과 인접 리스트

 

 

▷ 최고의 DFS /  BFS 글이라고 생각함....👍👍

PS를 하며 느끼는 DFS와 BFS 선택의 기준