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

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

✅ 문제 설명

✅ 풀이

우선 이 문제를 직접 풀지 못했다. 해당 문제는 최소 신장 트리 문제다.

• 최소 신장 트리

  
  그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우(사이클)에는 최소한의 연결이라 말할 . 수없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 . 단한 가지로 결정되도록 항상 트리의 형태를 나타낸다.최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다.

최소 신장 트리를 만드는 알고리즘으로는 대표적으로 크루스칼 알고리즘, 프림 알고리즘이 있다. 이번 문제는 크루스칼 알고리즘을 활용해 문제를 푸는 방법을 참고 했다.

• 크루스칼 알고리즘

  크루스칼 알고리즘은 우선 그래프 간선들을 가중치를 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다. 이때 사이클이 형성되는지의 여부를 판단하기 위해서 Union & Find 연산이 필요하다.
  Union & Find 연산은 자기 사진을 부모로 가지도록 초기화 된 배열을 만들고, 연결 된 두 정점의 부모를 비교하여 부모가 더 큰 노드를 작은 부모의 값으로 바꾸면서 연결 되어있음을 설정하는 연산법이다. 이 문제로 돌아와서 크루스칼 알고리즘을 적용시키면 우선, 비용을 기준으로 오름차순 정렬을 한다. 그 후 사이클 여부를 확인하며 반복문을 진행한다.

✅ 코드

• 1. 간선을 비용기준으로 오름차순 정렬한다.
• 2. 연결된 두 정점의 부모가 같은지 확인해보고, 다르면(사이클이 없으면) 최종 정답 값에 추가. 같다면(사이클이 있으면) 부모 연결.

     function findParent(parent, point) {
       if (parent[point] == point) {
         return point;
       } else {
         return (parent[point] = findParent(parent, parent[point]));
       }
     }
     function unionParent(parent, a, b) {
       const parentA = findParent(parent, a);
       const parentB = findParent(parent, b);
       if (parentA < parentB) {
         return (parent[parentB] = parentA);
       } else {
         return (parent[parentA] = parentB);
       }
     }
     function solution(n, costs) {
       let answer = 0;
       let parent = Array(n)
         .fill()
         .map((obj, index) => index);
       costs.sort((a, b) => {
         if (a[2] == b[2]) {
           return a[0] - b[0];
         } else {
           return a[2] - b[2];
         }
       });
       for (const cost of costs) {
         if (findParent(parent, cost[0]) !== findParent(parent, cost[1])) {
           answer += cost[2];
           unionParent(parent, cost[0], cost[1]);
         }
       }
       return answer;
     }

도움 받은 곳

사진: https://www.postech.ac.kr/ppostechian-section/2021-%EC%97%AC%EB%A6%84%ED%98%B8-%EC%A7%80%EC%8B%9D%EB%8D%94%ED%95%98%EA%B8%B0-%E2%91%A1/
한빛미디어 유튜브 크루스칼 알고리즘: https://www.youtube.com/watch?v=Gj7s-Nrt1xE&t=495s