[알고리즘] 깊이/너비 우선 탐색(DFS/BFS)

hyeseungS·2022년 5월 1일

1. 깊이/너비 우선 탐색(DFS/BFS)란?

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)는 두가지 모두 그래프를 탐색하는 방법입니다.

그래프란, 정점(node)와 그 정점을 연결하는 간선(edge)로 이루어진 자료 구조의 일종. G = (V, E)
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 
    전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

참고 : 그래프와 트리의 차이

-> 그래프 중 방향성이 있는 비순환 그래프 : 트리

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

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동.

루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식.
현재 정점과 인접한 간선들을 하나씩 검사.
-> 아직 방문하지 않은 정점으로 향하는 간선이 있으면 그 간선을 무조건 따라감.
-> 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 뒤돌아감.
한 노드에서 제일 마지막 자식까지 탐색하고 돌아오는 과정을 '백트리킹(Backtracking)'

ex) 미로찾기
-> 최대한 한 방향으로 갈 수 있을 때까지 가다가 막다른 길이면 다시 가장 가까운 갈림길로 돌아와 그 갈림길부터 다시 다른 방향으로 탐색 진행.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택.
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단.
검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림.

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

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
각 정점을 방문할 때마다 모든 인접 정점들 검사
-> 이 중 처음 보는 정점 발견 시 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장
-> 인접 정점 모두 검사한 뒤, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문
(따라서, 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정됨)
다익스트라, 프림 알고리즘은 BFS를 근간으로 이루어진 알고리즘

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie 사이에 존재하는 경로를 찾는 경우
-> 깊이 우선 탐색 : 모든 친구 관계를 다 살펴봐야 할지도 모름.
-> 너비 우선 탐색 : Sam과 가까운 관계부터 탐색.

두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택.
너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡.
검색 속도 자체는 깊이 우선 탐색(DFS)에 비해서 빠름.

4. 깊이 우선 탐색(DFS) vs. 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)	너비 우선 탐색(BFS)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐로 구현

시간복잡도

조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도 동일.
다음 노드가 방문하였는지 확인하는 시간 + 각 노드를 방문하는 시간.
구현하는데 2가지 방법 : 인접 행렬, 인접 리스트

인접 행렬 : O(N^2)

인접 리스트 : O(N+E)
(N : 노드, E : 간선)

- 일반적으로 E(간선)의 크기가 N^2에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적.
- 인접 행렬 : 정점의 개수 N만큼 도는 2중 for문을 돌려 두 정점 간에 간선이 존재하는지 확인.
- 인접 리스트 : 존재하는 간선의 정보만 저장되어 인접 행렬에서 사용한 2중 for문 필요하지 않음. 
               다음 노드가 방문하였는지 확인할 때 간선의 개수인 E의 두 배만큼의 시간이 걸리고, 
               각 노드를 방문할 때 정점의 개수인 N만큼 걸림.

5. Java 코드

모든 정점은 3가지 상태를 거침
1. 아직 발견되지 않은 상태 (!check[i])
2. 발견되었지만 방문하지 않은 상태
3. 방문된 상태 (check[i])

DFS 알고리즘의 2가지 방법

스택 이용
재귀함수 이용 -> 가장 보편적, 짧은 코드 작성

// [재귀적 dfs]
// 인접 행렬 dfs
void dfs(int x) {

    check[x] = true;
    
    for(int i = 0; i < V ; i++) {
		if(graph[x][i] == 1 && !check[i]) { // 간선으로 이어져 있고 방문 안한 곳
			dfs(i);
		}
    }
}

// 인접 리스트 dfs 
void dfs(List[] list, int x) {

    check[x] = true;
    
    for(int i = 0; i < list[x].size(); i++) {
    	int next = (int) list[x].get(i);
        if(!check[next])
        	dfs(next);
    }
}

BFS 알고리즘은 큐(Queue) 이용
(현재 노드에서 인접해 있는 노드를 큐에 넣는 방식)

// [큐로 bfs 구현]
// 인접 행렬 bfs 
void bfs(int v, int start) {

    Queue<Integer> q = new LinkedList<>();
    boolean check[] = new boolean[v];
    
    check[start] = true;
    q.add(start);
    
    while(!q.isEmpty()) {
    	int now = q.poll();        
        for(int i = 0; i < v; i++) {
        	if(graph[now][i] == 1 && !check[i]) { // 간선으로 이어져 있고 방문 안한 곳
            	check[i] = true;
                q.add(i); // 방문 예정
            }
        }
    }
}

// 인접 리스트 bfs
void bfs(List[] list, int v, int start) {

    Queue<Integer> q = new LinkedList<>();
    boolean check[] = new boolean[v+1];
    
    check[start] = true;
    q.add(start);
    
    while(!q.empty()) {
    	int now = q.poll();
        for(int i = 0; i < list[now].size(); i++){
            int next = (int) list[now].get(i);
            if(!check[next]){
            	check[next] = true;
                q.add(next); // 방문 예정
            }
        }
    }
}