DFS와 BFS

출처 : https://namu.wiki/w/BFS

그래프를 탐색하는 방법은 DFS, BFS가 있다.

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,

그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

1. DFS (깊이 우선 탐색)

최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없으면 옆으로 이동하여 같은 방법으로 탐색

• 모든 노드를 방문하고자 하는 경우 이 방법을 선택
• BFS(너비 우선 탐색)보다 좀 더 간단하다는 장점이 있음
• 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느림
• 스택 또는 재귀 함수로 구현

2. BFS (너비 우선 탐색)

최대한 넓게(인접한) 탐색한 후 더 이상 갈 곳이 없으면 아래로 이동하여 같은 방법으로 탐색

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
• 큐를 이용해서 구현 (현재 정점에 연결된 가까운 점들부터 탐색)

3. DFS와 BFS의 시간 복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다. 따라서 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합치면 된다.

 

N은 노드 E는 간선이라고 가정할 때

• 인접 리스트로 구현 시
  그래프의 각 정점에 인접한 정점들을 연결 리스트(vector의 배열)로 표현하는 방법, 즉 정점의 개수만큼 인접 리스트가 존재한다.
  시간 복잡도 : O(N+E)
• 인접 행렬로 구현 시
  그래프의 연결 관계를 이차원 배열로 나타내는 방식
  시간 복잡도 : O(\( N^2 \))

=> 일반적으로 E(간선)의 크기가 \( N^2 \)에 비해 상대적으로 작기 때문에 인접 리스트 방식이 더 효율적

4. 문제 유형 / 응용

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  => DFS, BFS 중 어떤 방법을 사용해도 상관없음
• 경로의 특징을 저장해둬야 하는 문제
  => 예를 들어 각 정점에 숫자가 적혀있고, a ~ b까지 가는 경로는 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등
        각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용 (BFS는 경로의 특징을 가지지 못한다.)
• 최단거리를 구해야 하는 문제
  => 미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다.
       (DFS는 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
        BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 검색 시 먼저 찾아지는 해답이 곧 최단거리이다.)

Ex) https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

위 백준 문제가 가장 대표적이고, 간단한 DFS와 BFS 알고리즘 문제이다.

* 구현

1. 주어진 배열 데이터를 인접 리스트로 변환 후 연결된 데이터 정렬
2. DFS, BFS 구조를 이용해 알고리즘 구현

function solution(input) {
    let info = input.slice(0, 1)[0].split(' ')[2];
    let innerArr = new Object();

    input.slice(1).forEach((dr) => {
        let [d1, d2] = dr.split(' ');
        innerArr[d1] = innerArr[d1] ? [...innerArr[d1], d2] : [d2];
        innerArr[d2] = innerArr[d2] ? [...innerArr[d2], d1] : [d1];
    });

    for (let data in innerArr) {
        innerArr[data] = innerArr[data].sort((a, b) => Number(a) - Number(b));
    }

    console.log(DFS(innerArr, info));
    console.log(BFS(innerArr, info));
}

// 깊이 우선 탐색
function DFS(innerArr, curNode) {
    let visitedArr = []; // 방문한 노드를 담는 배열
    let needArr = [curNode]; // 방문할 노드를 담는 배열

    while (needArr.length !== 0) { // 방문할 노드가 없을 때까지
        let node = needArr.shift();
        if (!visitedArr.includes(node)) { // 방문한 적이 없는 경우
            visitedArr.push(node); // 방문한 노드에 추가
            
            // 하위 노드들을 먼저 탐색해야하므로 연결된 노드 배열을 앞에 넣어줌.
            needArr = innerArr[`${node}`] ? [...innerArr[`${node}`], ...needArr] : [...needArr];
        }
    }
    return visitedArr.join(' ')
}

function recursive_DFS(graph, v, visited = []) {
    visited.push(v); // 방문한 노드를 담는 배열
    for (let i = 0; i < graph[v].length; i++) { //그래프 데이터를 반복하며
        if (!visited.includes(graph[v][i])) { //방문하지 않은 노드가 있으면
            visited = recursive_DFS(graph, graph[v][i], visited); //방문 후 재탐색
        }
    }
    return visited
}



// 너비 우선 탐색
function BFS(innerArr, curNode) {
    let visitedArr = [];
    let needArr = [curNode];

    while (needArr.length !== 0) { // 방문할 노드가 없을 때까지
        let node = needArr.shift();
        if (!visitedArr.includes(node)) { // 방문한 적이 없는 경우
            visitedArr.push(node); // 방문한 노드에 추가
            
            // 현재 노드들을 먼저 탐색해야하므로 연결된 노드 배열을 뒤에 넣어줌.
            needArr = innerArr[`${node}`] ? [...needArr, ...innerArr[`${node}`]] : [...needArr];
        }
    }

    return visitedArr.join(' ')
}

위 문제의 예제 입력 1을 인접 리스트로 변환 시 { '1': [ '2', '3', '4' ], '2': [ '1', '4' ], '3': [ '1', '4' ], '4': [ '1', '2', '3' ] } 와 같이 나온다.

DFS경우 노드를 방문했을 때 각 노드와 연결된 노드들부터 탐색해야 하므로, visitedArr 배열 앞에 연결된 노드들을 넣어주고, 

BFS경우 노드를 방문했을 때 먼저 연결되어있는 노드들을 모두 탐색해야 하므로, visitedArr 배열 뒤에 넣어준다. 

 

* 참고  https://devuna.tistory.com/32

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