DFS/BFS 탐색 알고리즘

DFS/BFS

코딩 테스트를 치다보면 항상 DFS/BFS를 활용한 탐색 문제가 하나씩 나왔다.

DFS/BFS 개념과 자바 구현 방식을 한번 알아보자

 

 

1. 재귀함수

DFS 알고리즘을 구현하기 위해서 재귀함수를 사용하게 된다.

그럼 재귀함수란 무엇일까❔

 

영어로 Recursive Function 으로 재귀적이라는 의미 즉 자기 자신을 호출하는 함수를 의미한다.

단순하게 탈출 조건 없이 재귀문을 수행하면 무한히 반복하다가 최대 재귀 깊이에서 종료된다.

 

대표적인 재귀함수인 팩토리얼을 구현해보자

public class 팩토리얼 {
    public static void main(String[] args){
        int num = 5;
        int result = recursive_factorial(num);
        System.out.println(result);
    }

    public static int recursive_factorial(int num){
        if(num<=1){
            return 1;
        }
        return num * recursive_factorial(num-1);
    }
}

이런식으로 구현이 가능하다.

현재 숫자와 -1인 숫자를 재귀적으로 계속 호출하여 반복을 수행한다.

이떄 숫자 1보다 작아지면 즉 1이 되면 1을 반환하여 최종적으로 수식을 완성한다.

내가 생각하는 재귀문의 핵심은 어떤 값을 넣을거냐도 있지만 결국 탈출 조건이 잘 정해저야한다.

즉 반복적인 작업을 재귀를 통해서 가능하고 이렇게 했을 때 코드가 더 간결하게 만들어진다.

코딩테스트나 재귀를 사용하는 이유중 하나는 반복적으로 함수가 재귀 호출 될때 이 함수가 메모리에 스택으로 저장되게 되고 이런 특성을 이용하여 스택을 대신하여 사용할 떄 사용된다.

 

앞으로 알오볼 DFS 알고리즘의 스택을 이용하기 위해서 이 재귀를 이해하고 있어야한다.

2. DFS(Depth First Search)

DFS는 깊이 우선 탐색으로 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

스택 자료구조나 재귀를 이용하여 구현한다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택 최상단의 노드에 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
   방문하지 않는 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번 과정을 수행할 수 없을 때가지 반복

이런 그래프가 있을때 번호가 낮은 인접노드부터 시작해본다.

실제 코딩 테스트에서는 조건에 맞는 노드는 선택

각 단계별 방문 순서를 확인해보자

1. 노드 1 방문 처리
2. 노드 1 인접 노드 확인 -> 2번 노드 이동 (인접 가장 작은 노드로 이동)
3. 노드 2방문 처리 -> 인접 미방문 노드 확인 -> 노드 7 이동
4. 노드 7 방문처리 -> 인접 미방문 노드 확인 ->노드 6 이동
5. 노드 6 방문처리 -> 인접 미방문 노드 확인 -> 인접 미방문 X -> 스택 pop
6. 노드 7 -> 인접 미방문 노드 확인 -> 노드 8 이동
7. 노드 8 방문처리 -> 인접 미방문 노드 확인 -> 미방문 노드 있는 상황까지 pop
8. 노드 1 -> 미방문 노드 확인 -> 노드 3 이동
9. 노드 3 방문처리 -> 미방문 노드 확인 -> 노드 4 이동
10. 노드 4 방문처리 -> 미방문 노드 확인 -> 노드 5 이동

탐색 순서를 정리해보자

1 > 2 > 7 > 6 > 8 > 3 > 4 > 5 순서로 탐색이 진행된다.

 

이제 자바에서 어떤 식으로 구현되는지 한번 확인해보자

public class DFS구현 {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    public static void dfs(int x){
        visited[x] = true;
        System.out.println(x + " ");

        for(int i=0; i<graph.get(x).size(); i++){
            int y = graph.get(x).get(i);
            if(visited[i] == false)
                dfs(y);
        }
    }
}

이런식으로 스택 즉 방문관리를 boolean 배열로 사용

ArrayList를 중첩으로 사용해서 2차원 리스트를 구현한다.

이렇게 하는 이유는 ArrayList가 인덱스 접근에서 상수시간이 들기 때문에 직관적으로 빠르다

 

3. BFS(Breadth-First Search)

BFS 너비 우선 탐색이라고 불리며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 스택이 아닌 큐를 통해서 방문 처리를 수행한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정이 안될때 까지 반복 수행

이 그래프 상황을 다시 한번 가정해보자

방문 기준은 반호가 낮은 인접 노드부터 수행한다.

1. 시작 노드 1 큐 삽입 -> 방문 처리
2. 노드 1을 꺼내 방문 X 인접 노드 2,3,8 큐 삽입 후 방문 처리(삽입은 작은 순서로)
3. 노드 2를 꺼내 방문 X 인접 노드 7을 큐 삽입 후 방문 처리
4. 노드 3을 꺼내고 방문 X 인접 노드 4,5 큐 삽입 후 방문 처리
5. 노드 8을 꺼내고 방문 X 노드 확인 
6. 노드 7을 꺼내고 방문 X 인접 노드 6 큐 삽입 후 방문 처리
7. 노드 4 꺼내고 인접 노드 확인 
8. 노드 5 꺼내고 인접 노드 확인
9. 노드 6 꺼내고 인접 노드 확인 후 종료

최종 탐색 순서는 1 > 2 > 3 > 8 > 7 > 4 > 5 > 6 

너비 우선 탐색으로 가까운 노드를 우선한다.

핵심은 큐를 통한 방문 처리를 수행하기에 근처 노드를 기준으로 처리할 수 있는 것이다.

 

자바 코드로 한번 확인해보자

 public static void bfs(int x){
        queue.offer(x);
        visited[x] = true;

        while(!queue.isEmpty()){
            int y = queue.poll();
            System.out.print(y + " ");
            for(int i=0; i<graph.get(y).size(); i++){
                int node = graph.get(y).get(i);
                if(!visited[node]){
                    queue.offer(node);
                    visited[node] = true;
                }
            }
        }
    }

 

위 그림과 같이 큐를 통해서 인근 노드를 방문 처리 및 추가하는 것이 핵심 구현이다.

실제로 BFS,DFS 문제는 2차원 배열에서 좌표로 접근하는 문제들이 나온다. 

단순하게 인근 노드 번호만 사용하는게 아닌 좌표를 통해서 접근 하는 것도 확인 필요하다.