DFS와 BFS

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 탐색알고리즘 중 대표적인 그래프 탐색알고리즘으로 DFS와 BFS가 있다.

---

DFS (Depth-First Search)

DFS는 깊이우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택을 이용해서 구현할 수 있으나 재귀함수는 실행되는 과정이 스택과 같이 먼저 호출한 함수가 제일 나중에 실행되는 특징이 있기때문에 대부분 스택보다는 재귀함수를 이용해서 구현한다.

구체적인 동작과정은 다음과 같다.

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

자바(Java)로 작성한 코드는 다음과 같다.

public class Main {
    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.print(x + " ");
        for(int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if(!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        /*
            그래프 연결되는 내용 생략
         */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0; i < m; i++) {
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        dfs(1);
    }
}

불린객체를 노드의 갯수만큼 만들어 초기화 해주고 그래프를 표기할 때는 2차원 리스트 대신에 ArrayList를 2차원의 형태로 중첩해서 사용한다. ArrayList 또한 특정원소에 접근하기 위해서 상수 시간이 소요되기 때문에 일반적인 배열대신에 ArrayList를 사용할 수 있다. 

---

BFS (Breadth-First Search)

BFS(Breadth-First Search)는 이름 그대로 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐 자료구조를 이용하여 구현하며 구체적인 동작 과정은 다음과 같다.

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

특정 조건에서의 최단 경로 문제를 해결하기 위한 문제에서 효과적으로 사용될 수 있다.

자바 코드로 작성한 내용은 다음과 같다.

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        visited[start] = true;
        while(!q.isEmpty()){
            int x = q.poll();
            System.out.print(x + " ");

            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]){
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
		...
    }
}

첫번째로 방문한 노드 start를 큐에 넣고 방문 처리한 다음 start에 인접한 노드중에서 방문하지 않은 노드가 있다면 큐에 넣고 방문처리하는 과정을 큐가 빌 때까지 반복한다.