BFS(Breadth-first Search), DFS(Depth-First Search) 너비우선 탐색, 깊이탐색

 

알고리즘 문제에서 자주 등장하는 단골손님 입니다.

탐색(Search)이란 그래프 구조형태의 데이터에서 특정 데이터를 찾거나 서로의 연결 상태를 확인하기 위한 방법으로 알려져 있습니다.  * 물론 그래프 형태의 데이터구조에서만 사용되지는 않습니다

 

단순한 반복문이나 조건문으로 이루어진 알고리즘이 아니기 때문에 처음 접근하기에는 난이도가 있다고 생각 합니다.

또한 그래프(graph)구조를 2중배열로 표현하는 방법을 만나기 때문에 다차원배열에 대해서 경험이 적다면 역시나 어려울 수 있습니다.

 

아래와 같은 데이터 구조가 있다고 가정하여 봅니다.

 

숫자 1은 숫자 2,4와 연결되어 있습니다.

숫자 2는 1,3,4와 연결되어 있습니다.

숫자 3은 2,4와 연결되어 있으며,

숫자 4는 1,2,3과 연결되어 있습니다.

1 -> 2, 4
2 -> 1, 3, 4
3 -> 2, 4
4 -> 1, 2, 3

 

이러한 데이터 구조를 그래프(graph)라고 하며 2차원 배열로 표현 할 수 있습니다.

2차원 배열에서 첫번째 값은 자기 자신을 의미 합니다.

int [][] array = new int[5][5];

array[1][1] => 1번 값의 1번친구
array[2][1] => 2번 값의 1번친구
array[2][3] => 2번 값의 3번친구
array[2][4] => 2번 값의 4번친구
...

 

위 내용처럼 2차원 배열에서의 첫번째 배열의 숫자는 그래프에서의 자기 자신을 의미 합니다.

1번째 값에서 2번과 4번끼리 서로 연결되어 있는 상태 라면 이때 값을 1을 넣어주도록 합니다.

배열에서의 크기를 설정하고 값을 따로주지 않으면 숫자 0이 들어가게 됩니다.

 

 

배열의 사이즈가 5인 이유는 1,2,3,4 데이터를 표현하기 위해서 입니다.

0번값은 사용하지 않고 숫자로 직접적으로 표현하기 위해서 입니다.

 

배열의 첫번째 숫자 1은아래와 같이 데이터를 저장하고 있습니다.

array[1] = [0, 0, 1, 0, 1]

숫자 1은 2와 4를 가지고 있기 때문에 아래처럼 데이터를 넣어 줍니다.

array[1][2] = 1

array[1][4] = 1

 

이러한 방식으로 그래프형태의 데이터는 채워져 있습니다.

 

* BFS(Breadth-first Search)

너비 우선 탐색은 1개의 대상의 데이터에서 연결된 데이터를 가져와서 먼저 찾는 것 입니다.

숫자 1은 2번과 4번을 가지고 있습니다.

 

array[1] = [0, 0, 1, 0, 1]

 

BFS 방법을 활용해서 서로의 데이터의 관계를 연결하거나 데이터를 찾기 위해서는 1개의 행이 바라보는 데이터를 전부 가져와서 해당 값에대한 연결여부를 확인하면 됩니다.

 

1. 시작 데이터를 정합니다

2. 데이터를 큐에 담은 뒤에 확인하였다는 흔적을 추가 합니다

3. 시작 데이터가 바라보는 데이터를 전부 조사하여 큐에 넣어주며 흔적을 추가 합니다

 

숫자 1을 시작점으로 위 3단계를 아래처럼 진행하여 봅니다.

 

이렇게 넣어진 데이터는 1개의 행이 전부 확인됨을 알 수 있습니다.

큐(Queue)를 사용하는 이유는 먼저 찾은 데이터가 다음번에 위 단계를 진행할 수 있게 하기 위함입니다.

 

흔적을 기록하는 것은 해당 값이 조사가되었음을 확인한 경우 반복문에 의해서 더 이상 나오지 않게하기 위해서 입니다.

단순한 논리식 배열을 사용하면 쉽게 구현할 수 있습니다.

 

이러한 개념은 아래 코드로 표기할 수 있습니다.

private static int [][] array;


public static void main(String[] args) {
    int size = 4;
    array = new int[size+1][size+1];

    array[1][2] = 1;
    array[2][1] = 1;
    array[2][3] = 1;
    array[3][2] = 1;

    array[4][1] = 1;
    array[4][2] = 1;
    array[4][3] = 1;

    array[1][4] = 1;
    array[2][4] = 1;
    array[3][4] = 1;		

    boolean history[] = new boolean[size+1];    

    bfs(history, 1);
}

//넓이 우선 탐색
private static void bfs(boolean history[], int cursor) {

    PriorityQueue<Integer> que = new PriorityQueue<>();

    //첫 시작
    que.offer(cursor);
    history[cursor] = true; //들어온 첫번째 값의 탐색은 끝났습니다.

    while(!que.isEmpty()) {
        int index = que.poll();
        for(int i=1;i < array.length; i++) { //해당 값의 행에 해당하는 데이터를 가져옵니다
            if(array[index][i] == 1 && history[i] == false) {  
                que.offer(i);
                history[i] = true;	
            }
        }
        System.out.println(index);
    }
}

 

* DFS(Depth-First Search)

깊이탐색은 너비우선탐색과 반대되는 개념으로 연결 대한 연결, 더 이상 찾는 값이 없을 때 까지 찾는것을 의미 합니다.

너비우선 탐색은 1개의 행을 찾는 개념이면 깊이탐색은 횡으로 아래로 내려가는 개념이라 볼 수 있습니다.

 

1. 시작 데이터를 정합니다

2. 시작데이터에서 연관된 데이터를 조사합니다.

3. 연관된 데이터가 나오는경우 해당 데이터를 다시 시작데이터로 정하여 연관데이터를 조사합니다.

4. 이때 시작데이터는 더 이상 조사하지 않도록 흔적을 기록 합니다.

 

마찬가지로 숫자 1을 가지고 진행하여 봅니다.

 

너비우선탐색이 1개행을 전부조사한 뒤에 반복문을 동작시킨 것에 비해,

깊이탐색은 연관된 데이터를 발견한 경우, 해당 데이터를 다시 키 값으로 활용하여 해당 키 값에 대한 다음 데이터가 있는지 조사하는 방법 입니다.

private static int [][] array;


public static void main(String[] args) {
    int size = 4;
    array = new int[size+1][size+1];

    array[1][2] = 1;
    array[2][1] = 1;
    array[2][3] = 1;
    array[3][2] = 1;

    array[4][1] = 1;
    array[4][2] = 1;
    array[4][3] = 1;

    array[1][4] = 1;
    array[2][4] = 1;
    array[3][4] = 1;		

    boolean history[] = new boolean[size+1];    

    dfs(history, 1);
}


//깊이우선탐색
private static void dfs(boolean history[], int cursor) {
    history[cursor] = true;
    System.out.println(cursor);  

    for(int j=1;j < history.length; j++) {
        if(array[cursor][j] == 1 && history[j] == false) {  //대상 값이면,
            dfs(history, j);
        }
    }
}

 

여기서 어려운 부분이 바로 재귀(Recursive) 동작 입니다.

자기 자신을 계속해서 호출하므로 처음 연습을 하게되면 스택오버플로우 오류를 자주 만나볼 수 있습니다.

 

* 재귀함수 관련 글

https://lts0606.tistory.com/509

자바로 살펴본 재귀 함수의 동작 방법 - 1 (Java Recursive method)

 

소스코드는 제 깃허브에서 받아보실 수 있습니다.

https://github.com/TaeSeungRyu/sample/tree/main/프로그래머스

GitHub - TaeSeungRyu/sample

 

너비우선 탐색과 깊이탐색은 알고리즘 문제에서 정말 단골손님입니다.

무방향, 방향, 가중치 그래프 등등 다양한 자료구조에서 데이터를 찾거나 관계를 그릴 때 사용됩니다.

어렵지만 코드를 계속해서 살펴보고 타이핑 하다 보면 어느순간에 감이오는 경우가 있습니다.

좀 더 익숙해지도록 노력해야겠습니다!

 

이상으로 BFS(Breadth-first Search), DFS(Depth-First Search) 너비우선 탐색, 깊이탐색에 대해서 살펴보았습니다.

궁금한점 또는 틀린부분은 언제든 연락주세요! 👻