2018 7급 국가직 기출풀이 - 자료구조론 마형 3번

문제 풀이에 앞서,

제 나름대로의 풀이를 두서없이 적은 것이며, 목적은 저처럼 혼자서 공시준비하는 사람들과 공유하고자 함입니다.

따라서 오류가 많을 수 있으니 틀린 부분이 있으면 댓글로 지적하며 의견을 나눠주세요.

아울러, 내용을 퍼가셔도 상관은 없으나, 원문 링크를 걸어주세요. (제가 피드백을 받을 수 있도록)

---

문제

문3. Prim 알고리즘을 사용하여 다음 가중 그래프(weighted graph)의 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선은? (단 시작 정점은 A이다)

[ 깨뱌 자체제작 자료 ]

① 42, (A, G)

② 43, (A, G)

③ 44, (F, G)

④ 45, (F, G)

---

정답

1번

---

풀이전 기초

* Prim 알고리즘

- 시작점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 가는 방법

1) 시작 : 시작 정점에서 인접 정점 중 최소 간선으로 연결된 정점 선택

2) 위와 같은 방식으로 모든 정점들이 연결되면 종료

 

* 신장 트리(Spanning Tree)

- 그래프 중 모든 정점이 간선으로 연결되어 있되, 간선간의 사이클이 없는 그래프

 

* MST(최소비용 신장트리)

- 각 정점을 모두 연결하면서 가장 낮은 비용으로 연결된 신장트리

- 깨뱌TIP : 굳이 모든 정점이 순서대로 연결되지 않아도 된다.

---

풀이과정

 

[ 꺠뱌 자체제작 자료 ]

검은선 - 연결 간선

빨간색 동그라미 - 연결 순서

---

G <-(마지막 연결) A(시작정점) -> B -> C -> E -> F -> D

=> 10 + 5 + 3 + 7 + 6 + 11 = 42

 

그래서! ① 42, (A, G) 이 정답!

---

마치며...

아이고 뭐라고 적어놨는지도 모르겠습니다.

제가 이해한대로 마구 풀어 쓴거라서 이게 맞는지도 모르겠습니다ㅠㅠ

우리 같이 화이팅 합시다!