🔎 섬 연결하기

❓ 문제링크

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

📄 제출 코드

function solution(n, costs) {
    var answer = 0;
    const parent = [];
    for (let i = 0; i < n; i++) {
        parent.push(i);
    }
    costs.sort((a, b) => a[2] - b[2]);
    for (const cost of costs) {
        if (!findParent(parent, cost[0], cost[1])) {
            answer += cost[2];
            unionParent(parent, cost[0], cost[1]);
        }
    }
    return answer;
}
function findParent(parent, a, b) {
    const n1 = getParent(parent, a);
    const n2 = getParent(parent, b);
    if (n1 == n2) return true;
    else return false;
}

function unionParent(parent, a, b) {
    const n1 = getParent(parent, a);
    const n2 = getParent(parent, b);
    if (n1 < n2) return parent[n2] = n1;
    else return parent[n1] = n2;
}

function getParent(parent, x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}
let n = 4;
let costs = [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]];
console.log(solution(n, costs));

처음에 2차원배열을 만들어 비용들을 넣어두고, 어떻게 시작해볼까 했는데 넣고나서 어떻게 찾아가야할지를 잘 모르겠었었다.
한참을 고민 하다가 결국 검색을 통해 찾아봤다.

union-find를 사용해 본 문제를 해결하였다.

// parent
// for (let i = 0; i < n; i++) {
//      parent.push(i);
//  }
    
const getParent = (parent, x) => {
  if(parent[x] === x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

처음 parent배열은 각자 자기 자신을 부모로 갖고 있는다.
두 노드가 연결 되있다면, 두 노드를 모두 동일한 부모로 변경해야 되는데 보통 더 작은 값으로 부모값을 지정한다.
본인이 아니라면 다음 x는 parent[x]로 전달하여 계속 상위로 탐색한다.

const unionParent = (parent, a, b) => {
  const n1 = getParent(parent, a);
  const n2 = getParent(parent, b);
  if(n1 < n2) return parent[n2] = n1;
  else return parent[n1] = n2;
}

부모를 병합하는 unionParent() 이다.
n1의 부모와 n2의 부모를 찾아 더 작은 값을 부모로 변경한다.

const findParent = (parent, a, b) => {
  const n1 = getParent(parent, a);
  const n2 = getParent(parent, b);
  if(n1 === n2) return true;
  else return false;
}

마지막으로 부모를 찾는 findParent()다.
두 노드의 부모를 찾고, 같으면 true, 다르면 false를 반환한다.

그럼 문제 해결을 하기 위해서 우선 cost가 낮은 순으로 정렬을 해주고,
cost를 돌면서, 두 개의 노드가 연결되어 있지 않다면 연결하고 그 간선의 가중치를 더해줄 것 이다. 그리고 이후 두 개의 노드는 서로 연결되었기 때문에 병합(union)해주면 된다.

이 부분이 마지막에 좀 이해가 잘 안되서 testcase를 그려봤다.
처음 정렬하게되면
costs 정렬
[ [ 0, 1, 1 ], [ 1, 3, 1 ], [ 0, 2, 2 ], [ 1, 2, 5 ], [ 2, 3, 8 ] ]

1. [0,1]
   parent = [0, 1, 2, 3]
   find : n1 = 0, n2 = 1, >> false
   answer + cost[2] = 0+1 = 1
   union : parent[n2] = n1 >> parent[1] = 0

2. [1,3]
   parent = [0, 0, 2, 3]
   find : n1 = 0, n2 = 3 >> false
   answer + cost[2] = 1+1 = 2
   union : parent[n2] = n1 >> parent[3] = 0

3. [0,2]
   parent = [0, 0, 2, 0]
   find: n1 = 0, n2 = 2 >> false
   answer + const[2] = 2+2 = 4
   union : parent[n2] = n1 >> parent[2] = 0

4. [1,2]
   parent = [0, 0, 0, 0]
   find: n1 = 0, n2 = 0 >> true

5. [2,3]
   parent = [0, 0, 0, 0]
   find: n1 = 0, n2 = 0 >> true

최종 answer = 4

📘 참고

https://velog.io/@longroadhome/프로그래머스-LV.3-섬-연결하기-JS