Programmers / Level 3 / 섬 연결하기 / JS

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

제한사항

다음과 같은 고려해볼만한 제한사항이 있다.

• 섬의 개수 n은 1 이상 100 이하입니다.

 

만약, 섬의 개수가 100을 넘어서 1,000 혹은 그 이상이라면,

간단한 kruscal 알고리즘 만으로는 풀이가 어려울 수 있다.

문제는 '시간복잡도' 때문이다.

 

kruscal 알고리즘에 사용되는 알고리즘인 union-find 알고리즘에서

부모노드를 찾기 위해, 계속해서 거슬러 올라가야 한다.

최악의 경우 여러 노드가 일렬로 연결되는데, 시간복잡도가 커지게 된다.

이 때, 'rank' 라는 개념을 도입해서 최적화를 진행하는데,

깊이가 작은 노드 집합을 깊이가 큰 노드 집합에 붙이게 된다.

 

이 문제는 이런 최적화까지는 하지 않아도,

범위가 작기 때문에 충분히 통과가 가능하니 다른 문제에서 설명하도록 하겠다.

 

풀이

function findParent(parent, n) {
  if (n === parent[n]) {
    return n;
  }

  parent[n] = findParent(parent, parent[n]);
  return parent[n];
}

function unionParent(parent, x, y) {
  const a = findParent(parent, x);
  const b = findParent(parent, y);

  if (a < b) {
    parent[a] = b;
  } else {
    parent[b] = a;
  }

  return parent;
}

function solution(n, costs) {
  const sortedCosts = [...costs].sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);

  let minCost = 0;

  for (const [x, y, cost] of sortedCosts) {
    const rootX = findParent(parent, x);
    const rootY = findParent(parent, y);

    if (rootX !== rootY) {
      unionParent(parent, rootX, rootY);

      minCost += cost;
    }
  }

  return minCost;
}

 

`findParent()`

function findParent(parent, n) {
  if (n === parent[n]) {
    return n;
  }

  parent[n] = findParent(parent, parent[n]);
  return parent[n];
}

 

`findParent()` 함수는 union-find 알고리즘에서 루트 노드를 찾는 함수이다.

`n`이 자기 자신을 부모로 가리키고 있다면,

그 노드가 해당 집합의 '루트'가 된다.

 

`unionParent()`

function unionParent(parent, x, y) {
  const a = findParent(parent, x);
  const b = findParent(parent, y);

  if (a < b) {
    parent[a] = b;
  } else {
    parent[b] = a;
  }

  return parent;
}

 

`unionParent()` 함수는 union-find 알고리즘에서 두 개의 서로 다른 집합을 하나로 합치는 역할을 한다.

 

먼저, 위에서 구현한 `findParent()` 함수로 두 노드의 루트 노드를 찾는다.

두 번째로, 인덱스가 더 큰 노드를 부모로 선택한다.

단순한 union 연산 구현으로, 최적화 할 시에 'rank' 개념을 도입해서 최적화가 가능하다.

 

`solution()`

function solution(n, costs) {
  const sortedCosts = [...costs].sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);

  let minCost = 0;

  for (const [x, y, cost] of sortedCosts) {
    const rootX = findParent(parent, x);
    const rootY = findParent(parent, y);

    if (rootX !== rootY) {
      unionParent(parent, rootX, rootY);

      minCost += cost;
    }
  }

  return minCost;
}

 

먼저, 간선의 cost 기준으로 오름차순으로 정렬해야 한다.

가장 저렴한 비용을 가진 간선부터 검토하기 위해서이다.

 

두 번째로, 자기 자신을 부모로 가지도록 초기화한다.

 

세 번째로, 사이클을 검사한다.

두 노드의 루트를 비교해서 다를 경우에 union 연산을 수행하게 된다.

만약 루트가 같다면, 같은 집합에 속해있다는 것이므로,

간선을 추가하면 사이클이 형성된다.

 

기존에 cost 기준 오름차순으로 정렬을 했고,

사이클이 형성되는지를 확인하기 때문에 cost를 더해주면 최소 비용을 얻을 수 있다.