[알고리즘] 최소 신장 트리

1. 최소 신장 트리(MST:Minimum Spanning Tree)
   1. 백트래킹에서 사용되는 용어
   2. 백트래킹 예시
      1. 1. N-Queen 문제
         1. 구현 코드
      2. 구현 코드
2. 관련 문제
   1. 문제1. 백준[2839] 설탕 배달
      1. 작성 코드
   2. 문제2. 백준[1931] 회의실 배정
      1. 작성 코드

최소 신장 트리(MST:Minimum Spanning Tree)

그래프상의 모든 노드들을 최소 비용으로 연결하는 방법

• 크루스칼^1, 프림^[2]

[2]:

백트래킹에서 사용되는 용어

• 유망(Promisiong): 해가 될 가능성이 있는 경우
• 가지치기(Pruning): 해가 될 가능성이 없는 경우 해당 노드를 제외
• 백트래킹(Backtracking): 유망하지 않은 쪽으로 가지 않고 되돌아 옴

[!Note] 재귀함수와 BFS를 잘 활용하자!!

백트래킹 예시

1. N-Queen 문제

구현 코드

---

구현 코드

---

관련 문제

문제1. 백준[2839] 설탕 배달

작성 코드

---

문제2. 백준[1931] 회의실 배정

작성 코드

---