자바스크립트 코딩테스트 강좌, 그래프의 표현

그래프의 정의

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조로, 정점은 객체나 노드를 나타내고 간선은 정점 간의 관계를 나타냅니다. 그래프는 방향이 있는 경우(Directed Graph)와 없는 경우(Undirected Graph)로 나눌 수 있습니다.

또한, 그래프는 가중치가 있을 수도 있고(Weighted Graph), 없을 수도 있습니다(Unweighted Graph). 가중치 그래프에서는 간선에 비용이나 거리가 할당됩니다.

그래프 표현 방법

그래프를 표현하는 방법은 크게 두 가지가 있습니다:

• 인접 행렬(Adjacency Matrix): 정점 간의 관계를 2차원 배열로 표현합니다. 배열의 크기는 정점의 수에 따라 결정되며, 행렬의 값은 두 정점 간의 간선의 존재를 나타내거나 가중치를 포함합니다.
• 인접 리스트(Adjacency List): 각 정점에 인접한 정점들을 리스트로 표현합니다. 이 방법은 메모리 효율성이 좋고, 희소 그래프에서 유리합니다.

문제: 그래프의 경로 찾기

다음 문제를 해결해 보겠습니다.

문제 설명: 주어진 그래프에서 두 개의 정점 A와 B가 주어질 때, A에서 B까지 가는 모든 경로를 찾아 출력하는 함수를 작성하세요.

그래프는 인접 리스트로 주어집니다.

문제 예시

입력:
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
}
start = 'A'
end = 'E'

출력:
['A', 'B', 'D', 'E']
['A', 'C', 'D', 'E']
            

문제 해결 과정

이 문제를 해결하기 위해 Depth-First Search(DFS) 알고리즘을 사용할 것입니다. DFS는 그래프의 깊이를 우선적으로 탐색하여 모든 가능한 경로를 찾아내는 알고리즘입니다.

1단계: DFS 함수 정의

먼저, 현재 정점에서 시작하여 모든 경로를 탐색하는 DFS 함수를 정의합니다. 이 함수는 현재 경로를 리스트로 가지고 있으며, 목표 정점에 도달하면 경로를 저장합니다.

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // 현재 정점을 경로에 추가

    // 목표 정점에 도달하면 경로를 저장
    if (start === end) {
        paths.push([...path]);
    } else {
        // 인접한 정점들에 대해 DFS를 호출
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths);
        }
    }

    path.pop(); // 경로에서 현재 정점을 제거 (백트래킹)
    return paths; // 모든 경로를 반환
}
            

2단계: 그래프와 입력값 정의

이제 그래프와 시작 및 종료 정점을 정의합니다.

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

const start = 'A';
const end = 'E';
            

3단계: 함수 실행

모든 경로를 찾기 위해 함수를 실행하고 결과를 출력합니다.

const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

최종 코드

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // 현재 정점을 경로에 추가
    if (start === end) {
        paths.push([...path]); // 경로가 완성되면 추가
    } else {
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths); // DFS 호출
        }
    }
    path.pop(); // 백트래킹
    return paths; // 모든 경로 반환
}

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

const start = 'A';
const end = 'E';
const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

결론

이번 포스팅에서는 자바스크립트를 활용한 그래프 표현 방식과 DFS를 이용한 경로 찾기 문제를 해결하는 과정을 설명했습니다. 그래프는 실생활에서도 다양한 문제를 해결하는 데 유용하게 사용되므로, 그 본질과 활용에 대한 이해는 매우 중요합니다. 앞으로 더 많은 알고리즘 문제를 다루어 보며, 다양한 문제 해결 능력을 기르시길 바랍니다.