자바스크립트 코딩테스트 강좌, 플로이드-워셜

작성자: 조광형

작성일: 2024년 11월 26일

1. 소개

코딩테스트에서 알고리즘 문제는 빈번하게 출제되며, 다양한 알고리즘을 이해하고 구현할 수 있는 능력이 중요합니다. 이 강좌에서는 플로이드-워셜(Floyd-Warshall) 알고리즘에 대해 다루고, 이를 자바스크립트로 구현하는 방법을 배웁니다. 플로이드-워셜 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 데 유용하며, 특히 대규모 그래프에 적합합니다.

2. 문제 설명

문제: 주어진 방향 그래프에서 모든 정점 사이의 최단 경로를 구하는 알고리즘을 작성하시오. 주어진 그래프는 가중치가 있는 간선으로 구성되어 있습니다. 만약 어떤 두 정점 사이에 경로가 없다면, 최단 경로의 값은 무한대로 처리합니다.


입력:
- 정점의 수 N (1 ≤ N ≤ 100)
- 간선의 수 M (1 ≤ M ≤ 10000)
- M개의 간선 정보 (A, B, C): A에서 B로 가는 가중치 C

출력:
- 목적지 정점 간의 최단 경로 길이를 나타내는 N x N 행렬을 출력하시오.

3. 플로이드-워셜 알고리즘 이해

플로이드-워셜 알고리즘은 동적 프로그래밍(dynamic programming) 기법을 활용하여 모든 쌍의 최단 경로를 계산합니다. 해당 알고리즘은 다음과 같은 단계를 포함합니다:

모든 정점 쌍 (i, j) 간의 초기 거리 값을 설정합니다. 직접 연결된 정점 간은 가중치를, 연결되지 않은 경우는 무한대(INFINITY)를 설정합니다.
각 정점을 중간 정점으로 설정하여, i에서 j로 가는 최단 경로를 체크합니다. 중간 정점을 k로 두고 i -> k -> j 경로가 i -> j 경로보다 짧은지 확인합니다.
이 과정을 모든 정점에 대해 반복합니다.

이렇게 함으로써 최종적으로 모든 정점 쌍 간의 최단 경로를 구할 수 있습니다.


function floydWarshall(graph) {
  const dist = JSON.parse(JSON.stringify(graph)); // 그래프를 복사하여 거리 행렬 초기화

  const n = graph.length; // 정점 수
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

4. 자바스크립트 구현

이제 플로이드-워셜 알고리즘을 자바스크립트로 구현해보겠습니다. 먼저 입력을 처리하고, 그래프를 초기화한 다음, 최단 경로를 계산하는 함수를 작성합니다:


function initializeGraph(N, edges) {
  const graph = Array.from({ length: N }, () => Array(N).fill(Infinity));
  for (let i = 0; i < N; i++) {
    graph[i][i] = 0; // 자기 자신으로 가는 경우는 0
  }

  edges.forEach(([A, B, C]) => {
    graph[A][B] = Math.min(graph[A][B], C); // 여러 간선이 있을 경우 최소 가중치로 업데이트
  });

  return graph;
}

// 문제를 해결하는 메인 함수
function solve(N, M, edges) {
  const graph = initializeGraph(N, edges);
  const shortestPaths = floydWarshall(graph);

  console.log("최단 경로 행렬:");
  shortestPaths.forEach(row => console.log(row.join(" ")));
}

5. 시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 O(N^3)입니다. 이는 N이 정점의 수일 때 각 정점 쌍을 확인하기 위해 3중 루프를 사용하기 때문입니다. 따라서 정점 수가 적당히 작은 경우 (100 이하) 효율적으로 사용될 수 있지만, 수백 이상의 정점이 있는 경우에는 다른 알고리즘을 고려해야 합니다.

6. 결론

본 강좌에서는 플로이드-워셜 알고리즘의 이론과 자바스크립트 구현 방법을 살펴보았습니다. 알고리즘의 이해 및 코드 구현 연습을 통해 코딩 테스트에서의 문제 해결 능력을 키울 수 있습니다. 다음 번에는 더욱 다양한 알고리즘을 다루어 보도록 하겠습니다.