[알고리즘] 그래프 탐색 알고리즘 by javascript - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

코딩 테스트의 단골 문제인 그래프 탐색 알고리즘에 대해 알아보자.

그래프 탐색 알고리즘의 개념을 이해하기 위해서는 당연히 그래프 자료구조를 알고 있어야 한다.

이 글은 자료구조를 알고 있다는 가정하에 탐색 알고리즘인 BFS와 DFS만을 정리하고자 한다.

(그래프에서는 인접행렬과 인접 리스트 방식이 존재하는데, 본 글은 인접 리스트를 사용한 BFS/DFS 알고리즘이다.)

1. BFS - 너비 우선 탐색

너비 우선 탐색 (Breadth-first search)은 정점들과 같은 레벨에 있는 즉, 인접한 노드들을 먼저 탐색하는 방식이다.

이미지를 통해 쉽게 접해보고 너비 우선 탐색의 특징에 대해 알아보자.

너비 우선 탐색은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법으로 두 개의 큐를 사용한다.
출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 해 메모리를 많이 잡아먹는다.

* 이미지 상 출력은 A - B - C - D - E - F - G - H - I - J - K로 출력된다.

▷ 너비 우선 탐색(BFS) 알고리즘 구현

// 인접 리스트 그래프
const graph = {
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "F", "G"],
    D: ["B", "H", "I"],
    E: ["B", "J"],
    F: ["C"],
    G: ["C", "K"],
    H: ["D"],
    I: ["D"],
    J: ["E"],
    K: ["G"],
};

const bfs = (graph, startNode) => {
    const visited = [];
    let needVisit = [];

    needVisit.push(startNode);
    while(needVisit.length !== 0){
        const node = needVisit.shift(); // queue의 선입선출로 shift() 사용
        if(!visited.includes(node)){
            visited.push(node);
            needVisit = [...needVisit, ...graph[node]];
        }
    }

    return visited;
}

두 개의 큐(visited, needVisit)를 사용해 너비 우선 탐색 알고리즘을 구현하였다.

선입선출이기 때문에 shift()를 이용해 앞에서부터 잘라서 비교해주는 로직이다.

2. DFS - 깊이 우선 탐색

깊이 우선 탐색 (Depth-first search)은 정점의 자식들을 먼저 탐색하는 방식이다.

이미지를 통해 쉽게 접해보고 깊이 우선 탐색의 특징에 대해 알아보자.

한 개의 큐와 한개의 스택을 사용한다.
단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
BFS보다 속도가 느릴 수 있으며, 보통 경로가 존재하는지를 판별할 때 사용된다.

* 이미지 상 출력은 A - B - D - H - I - E - J - C - F - G - K로 출력된다.

▷ 깊이 우선 탐색(DFS) 알고리즘 구현

// 인접 리스트 그래프
const graph = {
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "F", "G"],
    D: ["B", "H", "I"],
    E: ["B", "J"],
    F: ["C"],
    G: ["C", "K"],
    H: ["D"],
    I: ["D"],
    J: ["E"],
    K: ["G"],
};

const dfs = (graph, startNode) => {
    const visited = [];
    let needVisit = [];

    needVisit.push(startNode);
    while(needVisit.length !== 0){
        const node = needVisit.pop(); // stack의 후입선출로 pop() 사용
        if(!visited.includes(node)){
            visited.push(node);

            // graph[node].sort((a, b) => {
            //     if(a > b) return -1;
            //     else if (a < b) return 1;
            //     else return 0;
            // });

            needVisit = [...needVisit, ...graph[node]];
        }
    }

    return visited;
}

bfs와 구현하는 방식은 매우 유사하고 중간에 shift()냐 pop()이냐 정도만 바뀌면 그게 bfs인지 dfs인지 갈리는 것이다.

그리고 여기서 dfs 함수를 실행하면 다음과 같이 출력되는데,

['A', 'C', 'G', 'K', 'F', 'B', 'E', 'J', 'D', 'I', 'H'] 이는 이미지와 다르게 우측부터 시작해서 그렇다.

사실 우측이냐 좌측이냐 뭐가 먼저 실행되는지는 상관이 없지만 만약 좌측 우측 골라서 실행하고 싶으면 정렬을 해주면서 실행해 주어야 한다. (주석을 풀면 이미지와 동일한 방향으로 탐색을 진행할 것이다.)

일단 이렇게 구현은 됐는데, 그래프 탐색 알고리즘이라는 게 일단 이 정도만 알아두고 문제를 많이 풀어봐야 하는 알고리즘이라 그냥 무조건 문제를 많이 푸는 걸 추천한다.

참고 : 너비 우선 탐색 - 위키백과

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

ko.wikipedia.org

참고 : 깊이 우선 탐색 - 위키백과

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

깊이 우선 탐색의 애니메이션 예시 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작

ko.wikipedia.org