패스트캠퍼스 챌린지 20일차

---

Part 2. 알고리즘 이론

Ch 20. 그래프 고급 탐색 알고리즘

09. 프림 알고리즘 (2)

---

• 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함
• 프림 알고리즘 설명
  (1) 특정 노드를 선택한다.
  (2) 해당 노드/정점과 연결된 간선 중 가중치가 작은 간선과 연결한다.
  (3) 특정 노드와 연결된 노드의 간선 중 가중치가 작은 간선과 연결한다.
  (4) 가중치가 낮은 간선과 연결했으나 사이클이 생길 때 해당 노드 간의 연결은 제거한다.
  (5) (2)에서 (4)까지 과정을 반복하다 더이상 조건에 맞지 않아 연결할 노드가 없다면 종료한다. 
  
  
• 프림 알고리즘을 구현하는데 사용한 변수: currentEdge(현재 노드 정보), poppedEdge(우선순위 큐에서 가져온 노드), adjacentEdgeNode(간선으로 연결할 수 있는 인접한 노드),  currentEdgeList(현재 노드 목록), candidateEdgeList(연결할 수 있는 후보 노드 목록), adjacentEdgeNodes(인접한 노드 목록), priorityQueue(우선순위 큐)
  connectedNode(현재 연결된 노드),  mst(최종 목록 값), adjacentEdges(인근 노드 목록)

오늘은 프림 알고리즘을 코드로 구현했다. 블로그 글에 정보 + 후기를 담기위해 정보를 얹어야 하는데 코딩 위주로 수업한 날은 어떻게 써야 할까 고민하다 변수 목록을 적어보기로 했다. 물론 코드를 작성하는 방법에는 여러 개가 있고 그중 정답이 없다. 따라서 알고리즘을 공부하던 누군가가 우연히 내가 작성한 글을 보고 이해를 못 할 수 있다. 다만 대략적인 틀을 제공하면 그 안의 내용을 채우는 게 한결 수월해지는 것처럼 오늘 내가 배운 코드도 누군가에게 도움이 될 수 있도록 정리해봤다.

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-