15.섬 연결하기 - Greedy (Lv.3)

---

🔍 문제

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

---

📌 풀이

function solution(n, costs) {
  let answer = 0;
  // num 은 간선의 갯수
  let num = 0;

  // isVisited, isBridge 가 check 될 수 있게 각 크기에 맞게 falsely arr 생성
  let isVisited = Array.from({ length: n }, () => false);
  let isBridge = Array.from({ length: costs.length }, () => false);

  // 비용이 가장 작은 순서로 올림차순 정렬
  costs.sort((a, b) => a[2] - b[2]);

  // 처음에는 가장 비용이 작은 간선의 비용을 무조건 input 한다
  isVisited[costs[0][0]] = true;
  isVisited[costs[0][1]] = true;
  isBridge[0] = true;
  answer += costs[0][2];
  num++;

  // 간선의 개수가 노드의 개수 - 1 을 만족할때까지 while loop
  while (num < n - 1) {
    // 처음꺼 비용은 넣었으니 i = 1 부터 시작
    for (let i = 1; i < costs.length; i++) {
      // costs 의 각 구조분해 할당
      const [start, end, cost] = costs[i];
      // 다리가 건설되어 있지 않고 한쪽 노드만 방문한 경우를 찾기
      if (
        !isBridge[i] &&
        ((!isVisited[start] && isVisited[end]) ||
          (isVisited[start] && !isVisited[end]))
      ) {
        // 간선 추가 하고, 비용을 누적, 방문한것 start 와 end 지점 과 node 연결된거 true 하고 break
        num++;
        answer += cost;
        isVisited[start] = true;
        isVisited[end] = true;
        isBridge[i] = true;
        break;
      }
      console.log(isVisited);
    }
  }
  return answer;
}

let costs = [
  [0, 1, 1],
  [0, 2, 2],
  [1, 2, 5],
  [1, 3, 1],
  [2, 3, 8],
];
let n = 4;
console.log(solution(n, costs));

Reference

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