자바스크립트 코딩테스트 강좌, DFS와 BFS 프로그램

문제 설명

주어진 무방향 그래프에서 특정 노드까지의 최단 경로를 찾는 문제를 다루겠습니다. 그래프는 인접 리스트 형태로 주어지며, 최단 경로는 BFS로 구할 수 있습니다. DFS는 최단 경로를 찾기보다는 경로의 존재 여부를 확인하는 데 사용될 수 있습니다.

문제

입력:
- n: 정점의 수 (1 ≤ n ≤ 10^4)
- edges: 간선 리스트 (무방향)
- start: 시작 정점
- end: 종료 정점

출력:
- start에서 end까지의 최단 경로를 이루는 간선의 리스트
            

예시

입력: n = 5, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]], start = 1, end = 5

출력: [1, 2, 4, 5] 또는 [1, 3, 4, 5]

이론

DFS(깊이 우선 탐색)

DFS는 그래프의 한 노드에서 시작하여 가능한 한 깊숙이 탐색한 후 더 이상 진행할 수 없게 되면 되돌아가는 방식입니다. 이 알고리즘은 재귀적으로 또는 스택을 사용하여 구현됩니다. DFS의 장점은 메모리 사용량이 적고, 깊은 노드 탐색이 필요한 경우에 유용합니다.

BFS(너비 우선 탐색)

BFS는 시작 노드에서 인접한 모든 노드를 탐색한 후, 그 노드들의 인접 노드를 탐색하는 방식으로 진행됩니다. 큐를 사용하여 구현하며, 최단 경로를 찾기에 특히 적합합니다. BFS는 최단 경로를 찾는 데 있어 매우 유용하며, 최단 경로가 존재할 경우 이를 보장합니다.

문제 풀이

1단계: 그래프 구성

먼저, 인접 리스트를 사용하여 그래프를 구성해 보겠습니다.

function buildGraph(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u); // 무방향 그래프이므로 양방향으로 추가
    }
    return graph;
}

const n = 5;
const edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];
const graph = buildGraph(n, edges);
console.log(graph);
            

2단계: BFS 구현

이제 시작 정점에서 종료 정점까지의 최단 경로를 BFS로 찾아보겠습니다.

function bfs(graph, start, end) {
    const queue = [[start]];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const path = queue.shift();
        const node = path[path.length - 1];

        if (node === end) {
            return path; // 최단 경로를 찾으면 반환
        }

        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([...path, neighbor]); // 현재 경로에 인접 노드를 추가
            }
        }
    }
    return []; // 경로가 없을 경우 빈 배열 반환
}

const start = 1,
      end = 5;

const result = bfs(graph, start, end);
console.log(result);
            

3단계: DFS 구현

이제 DFS를 사용하여 경로의 존재 여부를 확인하고, 경로를 찾는 방법을 살펴보겠습니다.

function dfs(graph, start, end, visited = new Set(), path = []) {
    visited.add(start);
    path.push(start);
    
    if (start === end) {
        return path; // 경로를 찾으면 반환
    }

    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            const resultPath = dfs(graph, neighbor, end, visited, [...path]);
            if (resultPath.length > 0) {
                return resultPath; // 경로가 발견되면 반환
            }
        }
    }
    return []; // 경로가 없을 경우 빈 배열 반환
}

const dfsResult = dfs(graph, start, end);
console.log(dfsResult);