[Backend 개발자 면접 준비] DFS, BFS 알고리즘

DFS / BFS 알고리즘

DFS 와 BFS 알고리즘은 대표적인 그래프 탐색 알고리즘이다.

여기서 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

이제 이 두 알고리즘의 특징을 알아보도록 하자.

 

깊이 우선 탐색, DFS(Depth - First Search)

깊이 우선 탐색(DFS)은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 이다.

깊이 우선 탐색(DFS)은 실제 구현 시 재귀함수를 이용하므로 스택 오버플로에 유의해야한다.

 

코드로 DFS 구현 예시

public static void DFS(int item){
    if(!visited[item]){
        visited[item] = true;
        System.out.print(item+" ");
        for(int n : list[item]){
            if(!visited[n]){
                DFS(n);
            }
        }
    }
}

 

너비 우선 탐색, BFS(Breadth - First Search)

너비 우선 탐색(BFS)은 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

너비 우선 탐색(BFS)은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 너비 우선 탐색(BFS)은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

 

코드로 BFS 구현 예시

public static void BFS(int item){
    int first = (int)queue.poll();
    visited[first] = true;
    System.out.print(first+" ");
    for(int n : list[item]){
        if(!visited[n] && !queue.contains(n)){
            queue.add(n);
        }
    }
    if(!queue.isEmpty()){
        BFS((int)queue.peek());
    }
    else{
        return;
    }
}

 

	DFS	BFS
탐색 과정	시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색	시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문
특징	재귀 함수로 구현 스택 자료구조 이용	FIFO 탐색 Queue 자료 구조 이용
시간 복잡도	O(V(노드수) + E(에지수))	O(V(노드수) + E(에지수))

 

 

Reference Link

이지스퍼블리싱 - Do it 알고리즘 코딩테스트

https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS