2. Breadth/Depth First Search (BFS/DFS: 너비/깊이 우선 탐색)

정말 기본적으로 많이쓰이는 탐색 알고리즘 BFS, DFS 입니다.

제가 처음 알고리즘을 시작한것도 이 두 알고리즘으로 했습니다.

개념이나 기본 코드 자체는 간단한 편이에요.

저 같은 경우엔 초창기 이 알고리즘을 공부 할 때 조금만 난이도만 있어도 손도 못댄 기억이 납니다.

알고리즘도 수학과 마찬가지로 정확한 정의 또는 개념에서 시작한다고 생각이 됩니다.

(사실 잘 알고 있다 생각했음에도 상당히 문제를 풀지 못했고.. 현재도 많이 부족하다고 느낍니다. ㅠㅠ)

부족한 저를 위해서라도 다시한번 개념을 잡고 가보겠습니다. ^____^;

---

BFS DFS

완전 탐색 알고리즘

그래프, 트리, 행렬 등에서 주로 사용

이미 순서가 정해진 데이터를 탐색해 나가는 방법.

---

BFS (Breadth First Search)

너비 우선 탐색 알고리즘

• 시작점에서 그 시작점에 인접한 정점부터 순차적으로 탐색

DFS (Depth First Search)

깊이 우선 탐색 알고리즘

• 시작점에서 인접한 한 방향의 정점을 고르고 해당 방향의 뒤에 붙어있는 정점부터 우선 탐색

---

개념 자체는 간단하고 조금 애매하기도 합니다만, 그림을 그려보면서 확인해보면 이해가 빠를겁니다.

트리를 이용해서 한번 살펴 볼게요.

그전에, 먼저 아셔야 할 것이 BFS는 Queue, DFS는 스택 또는 함수로 구현됩니다.

• Queue: First in First out (FIFO), 삽입(offer), 삭제(poll)
• Stack(함수): Last in First out (LIFO), 삽입(push),  삭제(pop)

그러므로 그에 따른 탐색 순서도 잘 보셔야해요.

우선 두 경우 모두  트리는 15개, 행렬은 16개의 정점을 가진다고 가정하겠습니다.

출발은 1번 정점에서 시작하겠습니다.

그리고 만약 동등한 조건 내의 탐색이라면 정점 번호가 작은 것을 우선으로 하겠습니다.

Breadth First Search

1 단계

1. 우선 1번 정점을 큐에 담습니다.

2. 그리고 1번을 꺼내어 다음에 인접한 노드가 있는지 찾습니다.

3. 탐색 가능 정점은 2, 3이 존재합니다.

4. 하지만 아까위에서 가정 했었죠. 따라서 작은 번호를 가진 2부터 탐색합니다.

5. 따라서 2번 부터 큐에 담습니다.

2 단계

1. 너비 우선 탐색이니 다음으론 위에서 보류한 3번을 큐에 담아야겠죠.

2. 따라서, 다음은 4번이아닌 1과 인접한 정점인 3번을 탐색합니다.

3 단계

1. 이제 1과 인접한 정점은 모두 들어왔습니다.

2. 그럼 다음으로 2나 3에 인접한 정점을 넣어야 하겠죠?

3. 여기서도 아까 우리가 가정한 작은번호 먼저 탐색의 조건을 만족합니다.

4. 근데 이는 제가 의도적으로 넣은것이 아닙니다.

5. 6, 7 또는 4, 5가 탐색 되어야하잖아요. 4번 부터 탐색하는 이유는 아래와 같습니다.

1. 2번 먼저 큐에 담겼고 2가 큐에서 먼저 나오면서, 그때 2에 인접한 노드가 무엇인지를 먼저 탐색합니다.

2. 그래서 4번이 큐로 들어갑니다.

6. 물론 4, 5 중에 4가 들어가는 이유는 우리가 가정했던 '작은수 부터 탐색한다.'의 조건을 따릅니다.

4 단계

1. 이제 큐에는 3, 4가 들어와있고, 다음으로 5가 들어옵니다.

2. 4와 5는 아까 '2 단계'의 2와 3과 같은 관계인 셈이죠.

.

.

.

최종 단계

이렇게 위의 단계를 쭉 반복하다 보면 15번 정점까지 모두 완료 할 수 있습니다.

여기서 신경써서 보셨다면 아시겠지만, 제가 괜히 트리 마다 레벨을 붙여 놓은 것이 아닙니다. ㅎㅎ

BFS는 어떤 'level n'의 노드가 탐색이 완료되어야 그 다음 레벨로 넘어가는 것을 볼 수 있습니다.

탐색된 노드 순서

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15

큐에서 노드가 빠져 나오는 순서

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15

행렬에서 너비 우선 탐색

행렬도 마찬가지로 진행됩니다.

트리에서 동작하는 방식이 이해가 되셨다면, 그래프나 행렬도 문제는 없으실 겁니다.

행렬에서 BFS는 간단하게 과정에 대한 그림만 보여드리고 넘어가도록 하겠습니다.

행렬도 마찬가지로  BFS 기본 규칙은 따릅니다.

다만 작은 숫자부터 그 중 행과 열이 같은 조건이라면 행 부터 탐색하기로 합시다.

Depth First Search

1 단계

1. DFS도 1번부터 시작입니다.

2. 우선 1번을 스택에 담습니다.

3. 그리고 2번으로 접근하여 해당 정점을 스택에 담습니다.

2 단계

1. 다음엔 BFS와는 약간 다릅니다.

2. DFS는 같은 레벨의 다음 노드가 아닌 자신의 자식노드를 먼저(깊이) 탐색합니다.

3. 4, 5가 가능하겠지만 위에 말씀드린 조건에 따라 4번이 먼저 push 됩니다.

3 단계

1. 이제 4번까지 스택에 넣었는데요.

2. 그 다음으론 당연히 그의 자식 중 작은 번호, 정점 8번이 스택에 담기겠죠.

4 단계

1. 여기가 조금 중요합니다.

2. 이제 8번까지 가면 그 다음 자식 노드가 없잖아요?

3. 그래서 8번을 pop해서 스택에서 제거합니다.

4. 그리고 다시 스택의 꼭대기(peek)의 정점 번호를 가져오구요.

5. 해당 정점에서 다시 탐색 가능한 자식 노드가 있는지 확인해 봅니다.

6. 여기선 9번이 있네요. 따라서 9번을 스택에 담습니다.

최종 단계

말씀 드린대로 쭉 스택 또는 함수로 돌려보면 이러한 순서로 탐색을 하게 됩니다.

참고로 DFS는 스택보단 재귀 함수를 많이씁니다.

함수도 결국 스택처럼 담겼다가 반환되니까요.

순서가 단조롭진 않으니 이해가 안되신다면 그려보면서 생각해보세요!!

탐색된 노드 순서

1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 12 -> 13 -> 7 -> 14 -> 15

스택에서 노드가 빠져 나오는 순서

8 -> 9 -> 4 -> 10 -> 11 -> 5 -> 2 -> 12 -> 13 -> 6 -> 14 -> 15 -> 7 -> 3 -> 1

행렬에서 깊이 우선 탐색

행렬도 마찬가지로 진행됩니다.

DFS 또한 간단하게 과정에 대한 그림만 보여드리고 넘어가도록 하겠습니다.

행렬도 마찬가지로  DFS 기본 규칙은 따릅니다.

그리고 BFS와 마찬가지로 행 부터 탐색하겠습니다.

확실히 BFS와는 사뭇 다르게 탐색이 진행 됩니다.

여기서 5단계로 가면 다음 노드 탐색은 무엇이 될까요?

사실 행렬 탐색에선 방향 배열이라고 따로 생성하는 배열이 있습니다.

그 배열에 설정된 순서에 따라 진행이 될 텐데요.

다음 순서는 어찌되었든, 갈 수 있는 방향이 (3, 1) 밖에 없으니 그쪽으로 이동하게 되겠습니다.

이제 코드로 구현해보고 결과가 똑같이 나오는지 알아볼게요.

자바에선 트리나 그래프 형태의 탐색은 Adjacent List(인접 리스트)로 구현 합니다.

그점 참고하시고 봐주시길 바랍니다.

구조는 위에 트리와 같은 형태로 입력을 넣었고, 단방향으로 구성했습니다.

BFS 메소드

private static void breadthFirstSearch(int start) {        
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
        
    isVisited[start] = true;
    sb.append(start).append(SPACE);
        
    while(!q.isEmpty()) {
        int current = q.poll();
        if(tree[current] == null || tree[current].size() == 0) continue;
            
        for(int next: tree[current]) {
            if(isVisited[next]) continue;
            isVisited[next] = true;
                
            sb.append(next).append(SPACE);
            q.offer(next);
        }
    }
}
 

출력 결과 (방문 순서, 큐에서 나오는 순서)

isVisited 배열은 중복 방문을 피하기위해 체크하는 배열 입니다. (static으로 올려두었습니다.)

sb는 StringBuilder 객체를 받아온것이구요.

또한 BFS, DFS에서 동일하게 쓰이는 10번째 줄 예외 처리가 있는데요. 이건 예시에서만 필요한 처리입니다.

15번 이후 자식노드가 없는데 계속 접근 하려 할 수 있기 때문에 걸어 두었습니다.

'while(!q.isEmpty)'의 경우엔 큐에 데이터가 없는데 계속 접근하려하면 에러가 발생하므로 항상 해줘야하는 예외처리 중 하나입니다.

나머지 코드는 제가 설명한 이야기를 그대로 갖다 붙인거에요. ㅎㅎ

DFS 메소드

private static void depthFirstSearch(int current) {
    if(isVisited[current]) return;
    isVisited[current] = true;
        
    sb.append(current).append(SPACE);
        
    if(tree[current] == null || tree[current].size() == 0) return;
        
    for(int next: tree[current]) {
        if(isVisited[next]) continue;
            
        depthFirstSearch(next);
    }
}

출력 결과 (방문 순서)

출력 결과 (스택에서 빠지는 순서)

BFS/DFS.java 전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    private static ArrayList<Integer>[] tree = new ArrayList[16];
    private static boolean[] isVisited;
    private static StringBuilder sb;
    
    private static final String SPACE = " ";
    
    public static void main(String[] args) throws Exception{
        treeInit();
        
        sb = new StringBuilder();
        isVisited = new boolean[16];
        
        breadthFirstSearch(1);
        System.out.println(sb);
        
        
        sb = new StringBuilder();
        isVisited = new boolean[16];
        
        depthFirstSearch(1);
//        sb.append(1);                    스택에서 빠지는 순서로 데이터 출력 ...1
        System.out.println(sb);
    }
    
    private static void treeInit() {
        for(int i = 1; i < 8; i++) {
            tree[i] = new ArrayList<>();
            if(i > 8) continue;
            
            int sonNode = i * 2;
            for(int adder = 0; adder < 2; adder++)
                tree[i].add(sonNode + adder);
        }
    }
    
    private static void breadthFirstSearch(int start) {        
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        
        isVisited[start] = true;
        sb.append(start).append(SPACE);
        
        while(!q.isEmpty()) {
            int current = q.poll();
            if(tree[current] == null || tree[current].size() == 0) continue;
            
            for(int next: tree[current]) {
                if(isVisited[next]) continue;
                isVisited[next] = true;
                
                sb.append(next).append(SPACE);
                q.offer(next);
            }
        }
    }
    
    private static void depthFirstSearch(int current) {
        if(isVisited[current]) return;
        isVisited[current] = true;
        
        sb.append(current).append(SPACE);
        
        if(tree[current] == null || tree[current].size() == 0) return;
        
        for(int next: tree[current]) {
            if(isVisited[next]) continue;
            
            depthFirstSearch(next);
//            sb.append(next).append(SPACE);         스택에서 빠지는 순서로 데이터 출력 ...2
        }
    }
}

이대로 코드를 돌리시면 둘다 탐색 순서로 데이터가 출력됩니다.

• DFS에서 주석처리한 부분을 제거하시고
• DFS 메소드의 66번 줄을 주석처리하시면
• 스택에서 나오는 순서로 데이터를 출력 하실 수 있습니다.

스택 들어오고 나오는 동작은 Back Tracking 관련 자료도 정리하면서 더 자세히 해보겠습니다.

행렬로 탐색하기

그리고... 인접 행렬에서 구현도 빼먹으면 좀 아쉬우니까..ㅠㅠ

물론 문제 풀이에서 대부분 인접 행렬로 보여 드리겠지만,  간략히 해보겠습니다.

BFS, DFS 모두 실행 해볼게요.

우선 'DIRECTIONS'라는 배열을 잘 이해하셔야 합니다.

상수형 배열로 크기는 [4][2]로 잡힌 배열입니다. 고정 상수를 미리 넣어 주는데요.

static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

static final int ROW = 0, COL = 1;

그외에 아래 ROW, COL 이라는 정수형 상수도 잡아줍니다.

'DIRECTIONS'라는 배열은 말 그대로 방향을 잡고 움직이도록 도와주는 역할을 합니다.

위에 선언한 배열을 도식화 하면 아래와 같습니다.

DIRECTIONS	0번째 방향	1번째 방향	2번째 방향	3번째 방향
0 (ROW 상수)	1	0	-1	0
1 (COL 상수)	0	1	0	-1

여기서 0번째 방향부터 3번째 방향까지 각각 배열에서 {오른쪽, 아래, 왼쪽, 위}의 방향을 의미합니다.

기본적인 문제에서 n번째 방향에 어떤 방향 값을 넣어야할까 라는것은 크게 상관없습니다.

즉 순서 상관없이 그냥 골고루 입력만 잘해주시면됩니다.

위의 DIRECTIONS 배열은 위에서 말씀드렸는데 방향을 잡고 움직이도록 돕는다 했잖아요.

그래서 현재 내가 배열에서 위치한 곳과 더해서 사용합니다. 이에 대한 코드는 코드로 보여드릴게요.

우선 아래 그림에 대해 제대로 이해하고 넘어가시면 좀 더 코드 보시기가 편할 것 같습니다.

BFS 인접행렬

private static void bfs(int N, int M, char[][] map, Point start) {
    Queue<Point> q = new LinkedList<>();
    q.offer(start);                            // 시작 정점 담기
        
    isVisited[start.row][start.col] = true;
    map[start.row][start.col] = SEARCHED;
        
    while(!q.isEmpty()) {
        Point current = q.poll();
            
        for(final int[] DIRECTION: DIRECTIONS) {
            int nextRow = current.row + DIRECTION[ROW];
            int nextCol = current.col + DIRECTION[COL];
                
            // 다음 정점이 행렬 범위를 벗어나거나, 이미 방문 했다면 다음으로 넘어감
            if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
            if(isVisited[nextRow][nextCol]) continue;
            isVisited[nextRow][nextCol] = true;
                
            map[nextRow][nextCol] = SEARCHED;
                
            q.offer(new Point(nextRow, nextCol));
        }
    }
}

출력 결과

DFS 인접행렬

private static void dfs(int N, int M, char[][] map, int row, int col, int depth) {        
    map[row][col] = SEARCHED;
    if(depth < 4) print(map);
        
    for(final int[] DIRECTION: DIRECTIONS) {
        int nextRow = row + DIRECTION[ROW];
        int nextCol = col + DIRECTION[COL];
            
        if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
        if(isVisited[nextRow][nextCol]) continue;
        isVisited[nextRow][nextCol] = true;
            
        dfs(N, M, map, nextRow, nextCol, depth + 1);
    }
}

결과 출력

Main.java 전체 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    private static StringBuilder sb;
    private static boolean[][] isVisited;
    
    private static final char SEARCHED = '#';
    private static final char YET = '-';
    private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private static final int ROW = 0;
    private static final int COL = 1;
    
    private static class Point{            // 행과 열의 쌍을 저장하는 클래스
        int row;
        int col;
        
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    public static void main(String[] args) throws Exception{
        char[][] map = new char[4][4];
        
        for(int i = 0; i < 4; i++) {
            Arrays.fill(map[i], YET);
        }
        
        sb = new StringBuilder();
        isVisited = new boolean[4][4];
        
        bfs(4, 4, map, new Point(0, 0));
        System.out.print(sb);
        
        
        for(int i = 0; i < 4; i++) {
            Arrays.fill(map[i], YET);
        }
        
        sb = new StringBuilder();
        isVisited = new boolean[4][4];
        
        dfs(4, 4, map, 0, 0, 0);
//        print(map);
        System.out.println(sb);
    }
    
    private static void bfs(int N, int M, char[][] map, Point start) {
//        int count = 0;
        Queue<Point> q = new LinkedList<>();
        q.offer(start);                            // 시작 정점 담기
        
        isVisited[start.row][start.col] = true;
        map[start.row][start.col] = SEARCHED;
        
//        print(map);
        
        while(!q.isEmpty()) {
            Point current = q.poll();
            
            for(final int[] DIRECTION: DIRECTIONS) {
                int nextRow = current.row + DIRECTION[ROW];
                int nextCol = current.col + DIRECTION[COL];
                
                // 다음 정점이 행렬 범위를 벗어나거나, 이미 방문했다면 다음으로 넘어감
                if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
                if(isVisited[nextRow][nextCol]) continue;
                isVisited[nextRow][nextCol] = true;
                
//                if(count++ < 4) print(map);
                
                map[nextRow][nextCol] = SEARCHED;
                
                q.offer(new Point(nextRow, nextCol));
            }
        }
        
//        print(map);
    }
    
    private static void dfs(int N, int M, char[][] map, int row, int col, int depth) {        
        map[row][col] = SEARCHED;
//        if(depth < 4) print(map);
        
        for(final int[] DIRECTION: DIRECTIONS) {
            int nextRow = row + DIRECTION[ROW];
            int nextCol = col + DIRECTION[COL];
            
            if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
            if(isVisited[nextRow][nextCol]) continue;
            isVisited[nextRow][nextCol] = true;
            
            dfs(N, M, map, nextRow, nextCol, depth + 1);
        }
    }
    
    private static void print(char[][] arr) {
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr[i].length; j++) {
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }
        sb.append("\n");
    }
}

출력순은 1 -> 2 -> 3 -> 4 -> 최종 입니다.

저처럼 출력 해보시려면 코드에 주석처리된 부분을 지우고 실행하시면 됩니다.

와..우! 의도한건 아닌데 저 위에 그림으로 올린 탐색과 모두 똑같이 나왔네요 ㅎㅎ

시간 복잡도는 두 경우 모두 동일합니다.

인접 행렬: O(VE)

인접 리스트: O(V + E)

질문이나 틀린 부분 있으면 댓글 달아주세요!

빠르게 답변이나 보완하도록 하겠습니다. 감사합니다.