섬 연결하기

문제설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

문제설명

1. costs배열을 비용으로 정렬.
2. group을 두고 초기화를 시켜준다. 모든 섬이 연결되어있는지 확인하기 위해 필수.
3. 모든 섬이 연결될 때까지 while문을 돌려준다.(Set을 이용해 group의 원소 같은 숫자인지 확인)
4. costs배열에서 way를 뽑는다.
5. 서로 같은 그룹에 있는지 확인 같지 않으면,
   1. 각 그룹을 구하고, 한쪽 그룹으로 합쳐준다.
   2. answer에 비용을 더함.

function solution(n, costs) {
  let answer = 0;
  costs.sort((a, b) => b[2] - a[2]);
  let visited = Array.from(Array(n), (_, index) => index);
  while (new Set([...visited]).size !== 1) {
    const [landA, landB, cost] = costs.pop();
    const groupA = findGroup(visited, landA);
    const groupB = findGroup(visited, landB);
    if (groupA === groupB) continue;
    visited = visited.map((visit, index) => {
      return visit === groupB ? groupA : visit;
    });
    answer += cost;
  }
  return answer;
}

function findGroup(arr, land) {
  while (arr[land] !== land) {
    land = arr[land];
  }
  return land;
}

// function check(arr){
//     for(let i=0 ; i<arr.length-1 ; i++){
//         if(arr[i] === arr[i+1]) continue;
//         return true;
//     }
//     return false;
// }

아쉬운 점 || 느낀 점

처음에는 아 costs를 정렬하고, visited 배열을 만들어서 방문했는지 아닌지 확인하면 되겠구나!라고,
진짜 1차원적으로 생각해서 풀었는데, 당근 테스트케이스가 무더기로 틀렸다.
그래서 질문하기 탭에서 힌트를 받았는데, 그룹에 대한 내용을 봐서 풀었다.(사실 다른 사람 코드 살짝 구경함.)
자료구조, 알고리즘 시간에 크루스칼, 프림, 탐욕법을 하면서 그룹화해서 푸는 코드도 짜봤던 것 같은데,
까먹어서 못풀다니 너무 안타까웠다. 그래도 힌트를 보고 푼 것은 다행이다.