[프로그래머스💯][JS] 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

const makeDisjointSet = (islandList, n) => {
  for (let i = 0; i < n; i++) {
    islandList.push({
      me: i,
      pi: i,
      rank: 0
    })
  }
}

const findSet = (islandList, island) => {
  if (island.pi === island.me) return island
  else {
    return findSet(islandList, islandList[island.pi])
  }
}

const link = (island1, island2) => {
  if (island1.rank > island2.rank) island2.pi = island1.me
  else island1.pi = island2.me
  if (island1.rank === island2.rank) island2.rank += 1
}

const union = (islandList, island1, island2) => {
  link(findSet(islandList, island1), findSet(islandList, island2))
}

const costSort = arr => {
  const newArr = arr.sort((arr1, arr2) => {
    return arr1[2] - arr2[2]
  })
  return newArr
}

function solution(n, costs) {
  let answer = 0
  const islandList = []
  makeDisjointSet(islandList, n)
  const sortedCosts = costSort(costs)
  for (let edges of sortedCosts) {
    if (findSet(islandList, islandList[edges[0]]) !== 
    	findSet(islandList, islandList[edges[1]])) {
      answer += edges[2]
      union(islandList, islandList[edges[0]], islandList[edges[1]])
    }
  }
  return answer
}

 

---

풀이) 

 

이 문제는 Minimum Spanning Tree 알고리즘의 기초적인 개념과 일치합니다.

MST(Minimum Spanning Tree) 는 그래프 형태의 자료구조로 구성할 수 있는 가장 비용이 적은 트리를 구하는 알고리즘입니다.  저는 크루스칼 알고리즘과 disjoint set 자료구조를 이용해서 풀었습니다.

 

MST에 대해 기본 지식이 없으신 분들은 이 링크들 참고해주세요!

 

MST의 기본 개념:

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

MST - 크루스칼 알고리즘:

https://programming119.tistory.com/79?category=857952

[알고리즘] MST / Disjoint set / 크루스칼 알고리즘

 

Disjoint set :

https://ratsgo.github.io/data%20structure&algorithm/2017/11/12/disjointset/

Disjoint Set · ratsgo's blog

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges