05 : DFS, BFS

[Java 자료구조] DFS, BFS

---

 

1. DFS(Depth-First Search)

깊이 우선 탐색

 

스택을 사용

1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리하고,

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 모든 노드가 한번씩 방문되었으면 종료한다.

 

그래프의 노드 1을 시작 노드로 설정하여 DFS를 이용해 탐색

인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

방문 처리된 노드는 회색으로, 현재 처리중인 스택의 최상단 노드는 하늘색으로 표현한다.

 

step1. 시작 노드 '1'을 스택에 삽입하고 방문 처리

step2.  스택의 최상단 노드 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’ 중에서 가장 작은 노드 ‘2’를 스택에 넣고 방문 처리 

step3.  스택의 최상단 노드 ‘2’에 방문하지 않은 인접 노드 ‘7’을 스택에 넣고 방문 처리 

 

 

step4.  스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드 ‘6’과 ‘8’ 중에서 가장 작은 노드인 ‘6’을 스택에 넣고 방문 처리

 

 

step5.  스택의 최상단 노드 ‘6’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘6’번 노드를 꺼냄

 

 

step6.  스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드 ‘8’이 있으므로, ‘8’번 노드를 스택에 넣고 방문 처리 

 

 

step7.  스택 최상단 노드 ‘8’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘8’번 노드를 꺼냄

 

step8.  스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘7’번 노드를 꺼냄

 

 

step9.  스택의 최상단 노드 ‘2’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘2’번 노드를 꺼냄

 

step10.  스택의 최상단 노드 ‘1’에 방문하지 않은 인접 노드 ‘3’을 스택에 넣고 방문 처리

 

step11.  스택의 최상단 노드 ‘3’에 방문하지 않은 인접 노드 ‘4’, ‘5’ 중 가장 작은 노드 ‘4’를 스택에 넣고 방문 처리

 

 

step12.  스택의 최상단 노드 ‘4’에 방문하지 않은 인접 노드가 없으므로 4를 스택에서 뺀다.

최상단 노드가 3일때 방문하지 않은 인접노드 '5'를 스택에 넣는다.

 

 

step13.  남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.

 

위 단계에서 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다.

 

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

· 깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초하므로, 실제 구현은 재귀 함수를 이용했을 때 간결하게 구현할 수 있다.

· 소요시간: 데이터의 개수가 N개인 경우, O(N)

 

1) dfs 재귀 함수를 통한 예시 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static boolean [] visited = {
            false, false, false, false, false,
            false, false, false, false
    };
    public static int [][] graph = { {}, // 편의상 0번 인덱스 비움
            {2, 3, 8},
            {1, 7},
            {1, 4, 5},
            {3, 5},
            {3, 4},
            {7},
            {2, 6, 8},
            {1, 7}
    };

    public static void main(String[] args) {
        int start = 1; // 시작 노드
        dfs(start);
    }

    public static void dfs(int v) {
        visited[v] = true;  // 현재 노드 방문처리
        System.out.println(v + "");

        // 인접 노드 탐색
        for (int i : graph[v]) {
            // 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
            if (!visited[i]) {
                dfs(i);
            }
        }
    }
}

graph의 0번 인덱스는 편의상 비워두고, 1~8번 인덱스로 표현되어 있다.

각 인덱스가 노드 번호이며, 각 노드에 연결되어 있는 노드들의 정보라고 생각하면 이해하기 쉽다.

예를들어, 1번 인덱스에 {2, 3, 8}이 있으므로 1번 노드에 2, 3, 8번 노드가 연결되어 있다는 것이다.

이를 토대로 그림을 그리면 다음과 같다.

 

...

이런 순서대로 모든 노드를 방문하게 되면 순서는 다음과 같다.

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

2) dfs 스택을 이용한 예시 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static boolean [] visited = {
            false, false, false, false, false,
            false, false, false, false
    };
    public static int [][] graph = { {}, // 편의상 0번 인덱스 비움
            {2, 3, 8},
            {1, 7},
            {1, 4, 5},
            {3, 5},
            {3, 4},
            {7},
            {2, 6, 8},
            {1, 7}
    };

    public static void main(String[] args) {
        int start = 1; // 시작 노드
        dfs(start);
    }

    void dfs(int [][] graph, int start, boolean [] visited) {
        // 시작 노드 방문 처리
        visited[start] = true;
        System.out.println(start);

        Deque<Integer> stack = new LinkedList<>();
        stack.push(start); // 시작 노드를 스택에 넣기

        while(!stack.isEmpty()) {
            int now = stack.peek(); // 스택 최상단 요소 선택
            boolean hasNearNode = false; // 방문 안한 인접 노드 있는지 확인용
            for (int i: graph[now]) {
                if (!visited[i]) {
                    hasNearNode = true; // 방문 안한 노드 발견했으므로 true
                    stack.push(i);
                    visited[i] = true;
                    System.out.println(i);
                    break;
                }
            }
            // 방문하지 않은 인접 노드가 없으면 스택 최상단 요소 버리기
            if(!hasNearNode) stack.pop();
        }
    }
}

 

2. BFS(Breadth First Search)

너비 우선 탐색

가까운 노드부터 탐색한다.

선입선출의 큐를 이용 -> 인접 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가므로 가까운 노드부터 탐색하게 된다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문처리.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리.

3. 모든 노드를 방문할 때까지 1, 2를 반복.

 

노드 1을 시작으로 BFS 탐색 예시

숫자가 작은 노드부터 큐에 삽입하는것을 가정한다.

큐에 원소가 들어올 때, 위에서 들어오고 아래쪽에서 꺼낸다.

 

step 1.  시작 노드 ‘1’을 큐에 삽입하고 방문 처리 한다.

              방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표시하다.

step 2.  큐에서 노드 ‘1’을 꺼내고 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 모두 큐에 삽입하고 방문 처리한다.

 

step 3.  큐에서 노드 ‘2’를 꺼내고 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리 한다.

 

step 4.  큐에서 노드 ‘3’을 꺼내고 방문하지 않은 인접 노드 ‘4’와 ‘5’를 모두 큐에 삽입하고 방문 처리한다.

 

step 5.  큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

 

step 6.  큐에서 노드 ‘7’을 꺼내고 방문하지 않은 인접 노드 ‘6’을 큐에 삽입하고 방문 처리를 한다.

step 7.  남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례로 꺼낸다.

 

노드의 탐색 순서(큐에 들어간 순서) 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

· 너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다.

· 구현할 때는 언어에서 제공하는 큐 라이브러리를 사용하자.

· 탐색 수행 시간은 O(N)의 시간이 소요되고, 일반적인 경우 실제 수행 시간은 DFS보다 좋다.

    - 재귀 함수로 DFS를 구현하면 컴퓨터 시스템의 동작 특성상 실제 프로그램의 수행 시간이 느려질 수 있기 때문이다.

 

bfs 예시 코드

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    public static void main(String[] args) {
        int [][] graph = { {},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}
        };

        boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
        
        int start = 1; // 시작 노드
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        
        while(!queue.isEmpty()) {
            // 큐에서 노드 하나 뽑고 출력
            int v = queue.poll();
            System.out.println(v);
            
            // 인접한 노드중 방문 안된 노드들을 큐에 삽입
            for (int i: graph[v]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀함수 or 스택	큐

 

관련문제 

[Java] 백준 2667 : 단지번호붙이기 — 멋쟁이 노비처럼. (tistory.com)

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

[Java] 백준 1987 : 알파벳 — 멋쟁이 노비처럼. (tistory.com)

[Java] 백준 1987 : 알파벳

[Java] 백준 14226 : 이모티콘 — 멋쟁이 노비처럼. (tistory.com)

[Java] 백준 14226 : 이모티콘