자바스크립트 코딩테스트 강좌, 너비 우선 탐색

1. 문제 제기

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리 구조에서 유용하게 사용되는 탐색 알고리즘 중 하나입니다. 본 강좌에서는 BFS를 활용하여 “최단 경로 찾기” 문제를 해결해보겠습니다.

문제: 최단 경로 찾기

주어진 그래프에서 두 노드 사이의 최단 경로를 찾는 함수를 작성하시오. 그래프는 인접 리스트 형태로 주어지며, 노드는 문자열로 표현됩니다.

입력 형식

        graph: {
            "A": ["B", "C"],
            "B": ["A", "D", "E"],
            "C": ["A", "F"],
            "D": ["B"],
            "E": ["B", "F"],
            "F": ["C", "E"]
        }
        start: "A"
        end: "F"

출력 형식

        ["A", "C", "F"]

2. 문제 분석

최단 경로를 찾기 위해 BFS를 사용하는 이유는 BFS가 한 번에 모든 이웃 노드를 탐색하기 때문에, 가장 빠른 경로를 보장하기 때문입니다. DFS(깊이 우선 탐색)와 달리 BFS는 현재 노드에 연결된 모든 노드를 먼저 탐색한 후, 다음 레벨로 이동합니다. 이 특징으로 인해 BFS는 최단 경로 탐색에 적합합니다.

3. 알고리즘 설계

다음은 BFS를 이용한 최단 경로 찾기 알고리즘의 기본 흐름입니다:

  1. 시작 노드를 큐에 추가하고 방문 표시를 합니다.
  2. 큐에서 노드를 하나 꺼내고, 그 노드의 이웃 노드를 모두 확인합니다.
  3. 이웃 노드 중 방문하지 않은 노드를 큐에 추가하고, 해당 노드의 부모 노드를 현재 노드로 설정합니다.
  4. 종료 노드를 찾기 전까지 2-3 단계를 반복합니다.
  5. 종료 노드에 도달했을 때, 부모 노드를 거꾸로 탐색하여 최단 경로를 작성합니다.

4. 코드 구현

아래는 BFS를 이용한 최단 경로 찾기 함수의 구현 코드입니다:

        function findShortestPath(graph, start, end) {
            // 큐와 방문 표시를 위한 객체
            let queue = [start];
            let visited = {};
            let parent = {};
            
            visited[start] = true;
            parent[start] = null;

            while (queue.length > 0) {
                let currentNode = queue.shift(); // 큐에서 노드 제거
                
                // 종료 노드에 도달한 경우
                if (currentNode === end) {
                    return reconstructPath(parent, start, end);
                }

                // 현재 노드의 이웃들 탐색
                for (let neighbor of graph[currentNode]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        parent[neighbor] = currentNode; // 이웃 노드의 부모를 현재 노드로 설정
                        queue.push(neighbor); // 큐에 이웃 노드 추가
                    }
                }
            }
            return []; // 경로가 없을 경우 빈 배열 리턴
        }

        function reconstructPath(parent, start, end) {
            let path = [];
            let current = end;
            while (current !== null) {
                path.push(current);
                current = parent[current];
            }
            return path.reverse(); // 역순으로 경로 리턴
        }

5. 알고리즘 분석

위 코드는 최단 경로를 찾기 위해 BFS를 사용하고 있습니다. 시간 복잡도는 O(V + E)로, V는 노드의 수, E는 간선의 수를 의미합니다. 이 알고리즘은 인접 리스트를 활용하기 때문에 메모리 효율적인 장점이 있습니다.

6. 시간 복잡도와 공간 복잡도 분석

시간 복잡도는 O(V + E)로, 모든 노드와 간선을 한 번씩 탐색하기 때문에 이와 같은 복잡도가 발생합니다. 공간 복잡도 또한 O(V)로 큐와 방문 표시 배열, 부모 저장 배열 등이 노드 수에 비례하기 때문입니다.

7. 테스트 케이스

위 코드를 확인하기 위해 몇 가지 테스트 케이스를 만들어 보겠습니다.

        const graph = {
            "A": ["B", "C"],
            "B": ["A", "D", "E"],
            "C": ["A", "F"],
            "D": ["B"],
            "E": ["B", "F"],
            "F": ["C", "E"]
        };

        console.log(findShortestPath(graph, "A", "F")); // Output: ["A", "C", "F"]
        console.log(findShortestPath(graph, "B", "F")); // Output: ["B", "E", "F"]
        console.log(findShortestPath(graph, "D", "A")); // Output: ["D", "B", "A"]
        console.log(findShortestPath(graph, "A", "A")); // Output: ["A"]

8. 마무리

이번 강좌에서는 자바스크립트로 너비 우선 탐색(BFS)을 이용하여 최단 경로를 찾는 문제를 해결해 보았습니다. BFS는 인접 리스트와 같은 구조를 활용해 그래프를 탐색하는 유용한 방법이며, 다양한 문제에 응용될 수 있습니다. 앞으로도 알고리즘을 연습하며 더 많은 문제를 해결해 나가길 바랍니다.

9. 추가 자료

더 많은 알고리즘 문제와 해법을 학습하고 싶다면 온라인 코딩 테스트 플랫폼을 이용해 보세요. 각종 문제와 힌트 등을 통해 실력을 더욱 향상시킬 수 있습니다.

© 2023 자바스크립트 코딩테스트 강좌