가중치와 순서와 연결성 - 이름과 비용: 알고리즘 ep.04

같은 그래프라도 묻는 것이 달라지면 쓰는 도구가 달라집니다.

조건이 도구를 정합니다

ep.01 문제를 그래프로 바꿔 보기에서 본 너비 우선 탐색은 간선 비용이 모두 같을 때만 최단 거리를 보장합니다. 비용이 다르면 다른 도구가 필요합니다.

문제를 읽을 때 확인할 신호가 몇 가지 있습니다.

다익스트라는 확정된 정점을 늘려갑니다

다익스트라 알고리즘(Dijkstra’s algorithm) 은 시작점에서 각 정점까지의 최단 거리를 구합니다.

아직 확정되지 않은 정점 중 현재까지 알려진 거리가 가장 짧은 것을 꺼내 확정합니다. 그 정점을 거쳐 가면 더 짧아지는 이웃이 있으면 거리를 갱신합니다. 이 과정을 반복합니다.

거리가 가장 짧은 정점을 매번 꺼내야 하므로 우선순위 큐가 필요합니다. 자료구조 시리즈 ep.04 트리의 모양이 성능을 만든다에서 만든 최소 힙을 그대로 씁니다.

function dijkstra(graph, start, n) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap((a, b) => a.cost - b.cost);
  pq.push({ node: start, cost: 0 });

  while (pq.size > 0) {
    const { node, cost } = pq.pop();
    if (cost > dist[node]) continue; // 이미 더 좋은 경로로 처리된 항목

    for (const { to, weight } of graph[node]) {
      const next = cost + weight;
      if (next < dist[to]) {
        dist[to] = next;
        pq.push({ node: to, cost: next });
      }
    }
  }
  return dist;
}

cost > dist[node]로 걸러내는 줄이 중요합니다. 같은 정점이 큐에 여러 번 들어갈 수 있는데, 이미 더 짧은 경로로 확정된 항목은 버려야 합니다. 이 검사를 빠뜨리면 불필요한 갱신이 반복됩니다.

복잡도는 우선순위 큐를 쓸 때 O((V + E) log V)입니다.

지도 앱의 경로 안내가 이 계산입니다. 네트워크 장비도 같은 알고리즘을 쓰는데, OSPF는 각 링크의 비용을 간선 가중치로 두고 최단 경로를 구합니다.

음수 간선이 있으면 전제가 무너집니다

다익스트라는 한 번 확정한 정점을 다시 보지 않습니다. 이 결정이 안전한 이유는 간선 비용이 음수가 아니기 때문입니다. 앞으로 어떤 경로를 더해도 거리가 줄어들 수 없으니, 지금 가장 짧은 것이 최종적으로도 가장 짧습니다.

음수 간선이 있으면 이 논리가 깨집니다. 멀리 돌아가는 경로에 큰 음수 간선이 있으면 나중에 더 짧아질 수 있습니다.

벨만-포드 알고리즘(Bellman-Ford algorithm) 은 모든 간선을 정점 수만큼 반복하며 갱신해 이 경우를 처리합니다. 느리지만 음수 간선을 다루고, 갱신이 계속 일어나면 음수 사이클이 있다는 판정까지 할 수 있습니다. 복잡도는 O(V × E)입니다.

function bellmanFord(edges, start, n) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  // 정점 수 - 1번이면 모든 최단 경로가 확정된다
  for (let i = 0; i < n - 1; i++) {
    for (const { u, v, weight } of edges) {
      if (dist[u] === Infinity) continue;
      if (dist[u] + weight < dist[v]) dist[v] = dist[u] + weight;
    }
  }

  // 한 번 더 돌려서 갱신되면 음수 사이클이 있다
  for (const { u, v, weight } of edges) {
    if (dist[u] !== Infinity && dist[u] + weight < dist[v]) return null;
  }
  return dist;
}

반복 횟수가 정점 수 - 1인 이유는 최단 경로가 지나는 간선이 많아야 그만큼이기 때문입니다. 그보다 더 줄어든다면 같은 정점을 다시 지났다는 뜻이고, 그것이 음수 사이클입니다.

플로이드-워셜 알고리즘(Floyd-Warshall algorithm) 은 모든 정점 쌍 사이의 최단 거리를 한 번에 구합니다. 삼중 반복문 하나로 끝나 구현이 짧습니다. 대신 O(V³)이라 정점이 수백 개 이하일 때만 씁니다. 정점 500개면 삼중 반복문이 1억 2,500만 번이라 자료구조 시리즈 ep.01 크기가 접근법을 정한다의 기준선에 걸립니다.

// 거쳐 가는 정점 k를 가장 바깥에 두는 것이 핵심
for (let k = 0; k < n; k++)
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
      dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

반복문 순서가 바뀌면 틀립니다. k가 바깥에 있어야 “k번까지의 정점만 거쳐 가는 최단 거리”라는 단계적 확장이 성립합니다.

네 가지를 조건별로 정리하면 이렇습니다.

알고리즘	쓰는 조건	구하는 것	복잡도
너비 우선 탐색	간선 비용이 모두 같음	한 시작점에서의 최단 거리	O(V + E)
다익스트라	음수 간선 없음	한 시작점에서의 최단 거리	O((V + E) log V)
벨만-포드	음수 간선 있음, 음수 사이클 판정	한 시작점에서의 최단 거리	O(V × E)
플로이드-워셜	정점 수백 개 이하	모든 쌍의 최단 거리	O(V³)

연결 여부만 필요하면 거리는 계산하지 않습니다

두 정점이 이어져 있는지만 알면 되는 문제가 있습니다. 경로도 거리도 필요 없습니다.

유니온 파인드(union-find) 는 원소들을 그룹으로 묶고 두 원소가 같은 그룹인지 확인하는 데 특화된 구조입니다.

class UnionFind {
  #parent;
  #rank;

  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.#parent[x] !== x) {
      this.#parent[x] = this.find(this.#parent[x]); // 경로 압축
    }
    return this.#parent[x];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false; // 이미 같은 그룹

    // 낮은 트리를 높은 트리 아래에 붙인다
    if (this.#rank[rootA] < this.#rank[rootB]) {
      this.#parent[rootA] = rootB;
    } else if (this.#rank[rootA] > this.#rank[rootB]) {
      this.#parent[rootB] = rootA;
    } else {
      this.#parent[rootB] = rootA;
      this.#rank[rootA]++;
    }
    return true;
  }
}

두 가지 최적화가 들어가 있습니다. 경로 압축(path compression) 은 루트를 찾는 김에 거쳐 온 노드들을 루트에 직접 붙입니다. 랭크 기반 합치기(union by rank) 는 낮은 트리를 높은 트리 아래에 붙여 높이가 커지는 것을 막습니다.

둘을 함께 쓰면 연산당 비용이 사실상 상수에 가까워집니다. 정확히는 역아커만 함수라는 극히 느리게 증가하는 함수에 비례하는데, 현실적인 입력 범위에서는 4를 넘지 않는다고 알려져 있습니다.

같은 사람이 만든 계정 여러 개를 하나로 묶을 때 이 구조가 맞습니다. 이메일이나 전화번호가 겹치는 쌍을 발견할 때마다 합치고, 마지막에 같은 그룹인지만 물으면 됩니다. 이미지에서 서로 붙어 있는 픽셀 덩어리를 세는 계산도 같은 방식입니다.

최소 비용으로 전부 잇는 문제

모든 정점을 연결하되 간선 비용의 합을 최소로 만드는 것이 최소 신장 트리(minimum spanning tree) 입니다.

크루스칼 알고리즘(Kruskal’s algorithm) 은 간선을 비용 순으로 정렬한 뒤 싼 것부터 하나씩 추가합니다. 이미 연결된 두 정점을 다시 잇는 간선은 사이클을 만드니 건너뜁니다. 이 판정에 유니온 파인드를 씁니다.

function kruskal(n, edges) {
  edges.sort((a, b) => a.weight - b.weight);
  const uf = new UnionFind(n);
  let total = 0;
  let count = 0;

  for (const { u, v, weight } of edges) {
    if (uf.union(u, v)) { // 사이클이 아니면 채택
      total += weight;
      count++;
      if (count === n - 1) break; // 간선 n-1개면 완성
    }
  }
  return total;
}

프림 알고리즘(Prim’s algorithm) 은 정점 하나에서 시작해 트리에 붙일 수 있는 가장 싼 간선을 계속 고릅니다. 우선순위 큐를 쓴다는 점에서 다익스트라와 구조가 비슷합니다. 간선이 많고 조밀한 그래프에서는 프림이 유리하고, 희소한 그래프에서는 정렬 비용이 지배하는 크루스칼이 유리한 편입니다.

function prim(graph, n) {
  const inTree = new Array(n).fill(false);
  const pq = new MinHeap((a, b) => a.weight - b.weight);
  pq.push({ to: 0, weight: 0 }); // 아무 정점에서 시작
  let total = 0;

  while (pq.size > 0) {
    const { to, weight } = pq.pop();
    if (inTree[to]) continue; // 이미 트리에 있으면 버린다

    inTree[to] = true;
    total += weight;
    for (const edge of graph[to]) {
      if (!inTree[edge.to]) pq.push(edge);
    }
  }
  return total;
}

다익스트라가 시작점에서의 누적 거리를 큐에 넣는다면, 프림은 간선 하나의 비용만 넣습니다. 이 차이가 최단 경로와 최소 신장 트리를 가릅니다.

두 알고리즘 모두 그리디입니다. ep.03 언제 욕심내고 언제 기억하는가에서 본 탐욕 선택 속성이 증명된 사례입니다.

최소 신장 트리는 연결 비용을 줄여야 하는 설계에 씁니다. 지점 사이에 회선을 깔거나 센서를 잇는 계획에서 전체 길이를 최소로 만드는 계산이 그렇습니다.

순서 제약은 위상정렬입니다

작업 사이에 선행 관계가 있을 때 가능한 실행 순서를 찾는 것이 위상정렬(topological sort) 입니다. 빌드 의존성, 강의 선수 과목, 작업 스케줄이 여기 속합니다.

방향 그래프이면서 사이클이 없어야 성립합니다. A가 B를 요구하고 B가 A를 요구하면 순서를 정할 수 없습니다.

각 정점의 진입 차수를 세고, 진입 차수가 0인 정점부터 꺼내는 방식이 흔히 쓰입니다.

function topologicalSort(graph, n) {
  const indegree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    for (const v of graph[u]) indegree[v]++;
  }

  const queue = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

  const order = [];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);
    for (const v of graph[u]) {
      if (--indegree[v] === 0) queue.push(v); // 선행 조건이 모두 해소된다
    }
  }

  return order.length === n ? order : null; // null이면 사이클 존재
}

결과 길이가 정점 수보다 적으면 사이클이 있다는 뜻입니다. 순환 의존성 탐지를 함께 얻는 셈입니다.

빌드 도구가 매번 이 계산을 합니다. 번들러는 모듈이 서로를 import하는 순서를 위상정렬로 정하고, 데이터베이스 마이그레이션 도구는 먼저 적용해야 하는 스크립트를 같은 방식으로 찾습니다. 순환 의존성 오류는 정렬이 끝까지 가지 못했을 때 나옵니다.

참고 자료

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

다음 편 예고

ep.05 - 문자열 안에서 패턴 찾기

문자열에서 부분 문자열을 찾는 일은 이중 반복문이면 됩니다. 그보다 빠를 수 있는 이유는 실패한 비교에서 정보를 얻기 때문입니다. KMP의 실패 함수가 그 정보입니다.