[프로그래머스] 섬 연결하기

문제 풀이

이 문제는 유니온파인드와 최소신장트리 알그리즘인 크루칼 알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제다. 문제에서 주어진 노드와 노드 사이의 다리를 연결하는 비용이 주어지고, 모든 노드를 연결하는 다리를 건설하는데 비용을 최소로 하는 길을 만드는 문제다.

따라서 크루갈 알고리즘을 사용하면 최소 비용으로 모든 노드를 연결하면서 비용을 최소로 하는 길을 찾을 수 있따.

유니온 파인드

유니온 파인드에서 유니온은 합친다는 의미다. 파인드는 같은지를 확인하는 의미다.
유니온 파인드는 그래프 탐색에서 주로 활용되는 알고리즘이며 어떤 노드의 부모 노드가 같으면 같은 그래프 집합 그래프인 점을 활용하는 알고리즘이다.

1. 부모 노드가 없으면 자기 자신이 부모 노드가 된다.(최초값)
2. 각 그래프에서 가장 작은 값을 갖는 노드를 부모 노드로 설정한다.
3. 모든 노드를 반복문으로 순회하면서 각 노드가 속한 부모 노드에 관한 테이블을 생성한다.

크루칼 알고리즘

그래프 탐색에서 최소 비용으로 신장 트리를 만드는 알고리즘이다. 최소의 비용으로 모든 노드를 연결하는 그래프를 구성하는 알고리즘이다. 최소한의 비용으로 그래프를 구성하기 때문에 사이클이 발생하면 안된다. 싸이클 테이블을 통해서 모든 노드를 순회하면서 이미 그래프에 포함되어 있는지 유니온 파인드 알고리즘을 통해서 확인하면서 그래프에 노드를 추가하는 방법이다.

1. 노드와 간선 정보를 값, 거리, 비용이 적은 순으로 정렬한다.
2. 노드들을 순회하면서 비용이 적은 노드부터 그래프에 추가하고 싸이클링 테이블을 통해서 이미 추가된 노드는 추가하지 않는다.
3. 마지막 노드까지 추가하면 최소 비용으로 그래프가 완성된다.

제출 코드

function solution(n, costs) {
  // 유니온 파인드에서 부모 노드를 설정하는 함수
  const unionParent = (set, a, b) => {
    a = getParent(set, a);
    b = getParent(set, b);
    if (a < b) {
      set[b] = a;
    } else {
      set[a] = b;
    }
  };
  // 유니온 파인드에서 부모 노드가 같은지 확인하는 함수
  // 같은 그래프인지 확인하는 함수
  const hasEquelParent = (set, a, b) => {
    a = getParent(set, a);
    b = getParent(set, b);
    if (a === b) {
      return true;
    } else {
      return false;
    }
  };
  // 재귀적으로 부모 노드를 찾아내는 함수
  const getParent = (set, x) => {
    if (set[x] === x) {
      return x;
    }
    return getParent(set, set[x]);
  };

  let answer = 0;
  const table = Array.from({ length: n }, (_, i) => i);
  for (let [a, b, cost] of costs) {
    if (!hasEquelParent(table, a, b)) {
      answer += cost;
      unionParent(table, a, b);
    }
  }
  return answer;
}

출처
섬 연결하기https://school.programmers.co.kr/learn/courses/30/lessons/42861