This is my result of the individual project from Algorithm class CSCI 3101 Hawaii Pacific University.

알고리듬 수업에서 수행한 개인 프로젝트의 결과물입니다.

Freckles – Skiena and Revilla Programming Challenges book.

알고리즘 트레이닝 북에 실린 주근깨 문제입니다.

I implemented Prim and Kruskal algorithms for this project with Python. See attached files on the bottom of this post if you need.

You are allowed to edit attached source codes, but please do not remove my name as an author on the top.

참고로, 한국에서 판매하는 책에 해답(C로 작성된 소스코드)이 실려있지만, 실제로 작성해서 컴파일/실행해본 결과 제대로 작동이 되질 않았습니다. 따라서, 이것을 필자가 파이썬으로 재작성했고, 프로젝트의 조건은 Prim과 Kruskal 두 개의 알고리즘으로 구현해야하는 것이었습니다. 소스코드는 첨부된 하단에 파일을 참고해주세요. 내용은 수정해도 되지만, 제 이름은 삭제하지 말아주세요.

The below is the problem from the book.

아래는 알고리즘 트레이닝 북에 실린 문제의 원문입니다.

In an episode of the Dick Van Dyke television show, Dick’s son Richie connects the freckles on his father’s back to form a picture of the Liberty Bell. Consider Dick's back to be a plane with freckles at various (x, y) locations. Your job is to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

Input

The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.

The first line of each test case contains 0 < n <= 100, giving the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x, y) coordinates of the freckle.

Put a blank line between each two consecutive test cases.

Output

For each test case, your program must print a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. The output of each two consecutive cases must be separated by a blank line.

Sample Input

1

3
1.0 1.0
2.0 2.0
2.0 4.0

Sample Output

3.41 

---------------------------------------------------------------------------------------------------------

My source codes

Prim:

Kruskal:

HowItWorks.pdf

SeowonJung_Kruskal_Comment.py

SeowonJung_Prim_Comment.py