[Algorithm] MST

MST

MST는 모든 지점을 가장 적은 비용(minimize)으로 연결(spanning)하는 방법(tree)이다.

목표 : 도로나 인터넷 망을 모든 마을을 서로 연결하기 위함이다. 이때 공사비용도 적게 들여서 연결

tree의 의미 자체가 사이클(빙글빙글 도는 것) 없이 모든 점이 하나로 이어져 있는 구조이다.

MST는 가장 싸게 연결하는 트리를 의미한다.

• 모든 장소 연결 ⇒ 선(node)과 비용(weight)을 가장 적게

MST를 구하기 위한 방법에는 대표적인 2가지 알고리즘

• 크루스칼 알고리즘
• 프림 알고리즘

---

크루스칼 알고리즘

전체 지도를 먼저 보고, 가장 싼 길부터 선택한다.

• 도구 : union-find
  • 그룹 : 이미 서로 연결된 마을의 모임
  • Find : “이 마을이 어떤 그룹에 속해 있는가?” (=같은 그룹인가?)
  • Union : “아직 다른 그룹이라면, 하나의 그룹으로 합친다!”
• 사용법
  • 1. 모든 도로를 가격순으로 정렬한다. (제일 싼 도로부터 보기 쉽게!)
  • 2. 싼 도로부터 하나씩 고른다.
  • 3. 그 도로를 골랐을 때
       a. 만약 이미 연결된 마을끼리 다시 연결된다면 ❌ (사이클!)
       b. 아니면 연결 ✅
  • 4. 모든 마을이 다 연결될 때까지 반복

---

프림 알고리즘

아무 지점이나 잡고, 거기서부터 주변으로 확장해간다.

• 도구 : 우선순위 큐

  • 큐의 우선순위가 있는 것으로 가중치가 우선순위가 된다.
  • 큐에 연결할 수 있는 마을들의 (비용, 목적지)를 넣는다.
    

• 사용법

  • 1. 아무 마을을 하나 시작점으로 정한다.
  • 2. 그 마을과 연결된 도로 중에서 가장 싼 도로를 고른다.
  • 3. 그 도로를 통해 연결된 마을을 새로 그룹에 추가한다.
  • 4. 연결된 마을 전체에서 주변 마을로 가는 도로 중에서 가장 싼 것을 고른다.
  • 5. 모든 마을이 연결될 때까지 반복