[Algorithm] 프로그래머스 섬연결하기 - 크루스칼 알고리즘

크루스칼 알고리즘

크루스칼 알고리즘은,

탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하여 최적 해답을 구하는 것을 목적으로 한다. 크루스칼 알고리즘은 이미 최적의 방법이라는 것이 검증되었다.

섬 연결하기

프로그래머스 섬 연결하기 문제 풀러가기

이 문제는 크루스칼 알고리즘의 대표격인 문제가 아닐까 싶다.
크루스칼 알고리즘을 통해 각 섬을 연결하는 최소 비용, MST(최소 비용 신장 트리)를 얻는 것을 목표로 한다.

크루스칼 알고리즘인 만큼 Union-find 알고리즘에서 makeSet, union, find 함수를 적극 이용하는 방법이다.

/**
 * n = 4;
 * costs = [
 *   [0, 1, 1],
 *   [0, 2, 2],
 *   [1, 2, 5],
 *   [1, 3, 1],
 *   [2, 3, 8],
 * ];
 *
 * n: 섬의 개수
 * costs: 연결된 다리의 비용
 */
function solution(n, costs) {
  costs.sort(([, , a], [, , b]) => a - b);
  const MST = makeSet(n);
  let answer = 0;

  for (const [from, to, cost] of costs) {
    if (!(find(MST, from) === find(MST, to))) {
      union(MST, from, to);
      answer += cost;
    }
  }

  return answer;
}

function makeSet(n) {
  return [...Array.from({ length: n }).keys()];
}

function find(set, x) {
  if (set[x] === x) return x;
  set[x] = find(set, set[x]);
  return set[x];
}

function union(set, x, y) {
  const rootX = find(set, x);
  const rootY = find(set, y);
  set[rootY] = set[rootX];
}

크루스칼 알고리즘 동작은 다음과 같다.

- 그래프에서 연결된 간선을 모두 끊는다.
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
  - 가장 낮은 가중치를 먼저 선택한다.
  - 사이클을 형성하는 간선은 제외한다. (Union-find 알고리즘을 사용해야 한다.)
- 해당 간선을 현재 MST(최소 비용 신장 트리)의 집합에 추가한다.

위의 알고리즘 대로 과정을 알아보자면,

• 최소 비용 신장 트리를 얻기 위해선 기존의 그래프에서 간선을 모두 끊어야 한다. makeSet 함수를 통해 모두 끊어져 있는 그래프 집합을 생성한다.(makeSet은 배열을 반환하는데 배열의 인덱스는 섬의 번호를, 섬이 속하고 있는 집합의 부모 섬 번호를 의미한다. - 경로 단축 최적화 기법을 사용하여 부모 섬 번호가 아닌 속한 집합의 루트 번호를 가지고 있을 수 있다.)
• 가중치의 오름차순으로 정렬하는 것은 sort 메서드를 사용했다.
• 오름차순 순서대로 from, to, cost를 얻어 최소 비용의 간선을 연결한다. 이미 오름차순으로 정렬되어 있기 때문에 union 함수를 통해 섬을 연결하면 최소 비용부터 연결된다.
• find 함수를 통해 두 섬이 같은 집합에 연결된 상태인지 확인하여 같은 집합이라면 이미 최소 비용으로 연결된 상태이기 때문에 다시 연결할 필요가 없다. (같은 집합이라면 사이클이 생성되므로)

이렇게 모든 집합이 연결되면 MST를 얻을 수 있게 되는 것이다.

경로의 최소 비용의 합을 얻어야하므로 MST를 얻는 과정에서 answer에 cost를 누적하고 이를 반환하였다.

---

저번 시간에 정리한 Union-find 알고리즘을 정리하면서 크루스칼 알고리즘에 대해 알아보려고 했는데, 탐욕법 문제를 풀던 도중 이렇게 만나게 된 문제라 굉장히 흥미로웠다.