42861: 섬 연결하기

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

---

1. 문제

• n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
  
  다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

---

2. 문제의 조건

• 1  <= n <= 100
• costs <= ((n-1) * n) / 2
• 무조건 모든 섬은 연결이 되어있다.
• 양방향 가중치

 

---

3. 문제 접근

• 아이디어
  
  해당 문제는 최소신장트리 문제로 Prim 알고리즘과 Kruskal 알고리즘이 있습니다.
  Prim은 최소 heap을 이용하고 Kruskal은 DispointSet이라는 (union-find) 새로운 자료구조를 이용합니다.
  저는 최소 힙과 친하기에 최소힙을 이용한 Prim알고리즘을 이용하였습니다.
  최소신장트리는 순환구조가 되면 안되므로 이미 방문한 지점은 방문하지 않습니다. 그리고 Prim알고리즘은 간선을 기준으로 작업을 수행합니다.
  

  

  
  어떠한 지점부터 시작하든 상관없습니다.
  0번 노드부터 시작한다고 하면 heap에는 0에서 갈 수 있는 노드를 추가합니다. 0 -> 1과 0 -> 2이므로
  최소힙에는 (start, end, cost) : 0 1 1, 0 2 2가 등록됩니다. (간선의 가중치를 기준으로 최소힙)
  0 1 1이 pop되므로 방문지점인지 확인 후 방문을 안했으면 방문 등록을 합니다. cost 1
  그리고 0(start)로부터 왔으므로 1(end) 부터 갈 수 있는 위치를 등록합니다. (여기서 방문지점을 미리 제거해도되고 안해도됩니다.)
  그럼 1->3과 1->0, 1->2 가 등록됩니다.
  1 0 1, 1 3 1, 0 2 2, 1 2 5라고 치고 1 0 1을 부르면 0과 1은 이미 방문했으므로 넘어가고
  1 3 1이 선택됩니다. cost 2
  3에서는 3->1, 3->2를 갈 수 있고 이미 3->1에서는 방문했으니 생략하고 진행하겠습니다.
  그럼 0 2 2, 1 2 5, 3 2 8이 남게되고 0 2 2 가 pop이 되면서 cost 4가 되고 나머지의 2-> 2, 2->3 은 전부 방문 되어있으므로 생략됩니다.

 

---

4. 풀이 방법

• costs를 양방향으로 인접행렬로 만들어줍니다.
• 나머지는 아이디어 부분을 참고합니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/174

 

---

 

cjw.git@gmail.com