[백준 1774번] 우주신과의 교감

난이도: 골드 4

문제 링크: www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

백준 1774번: 우주신과의 교감

굉장히 재밌게 번역된 문제입니다.

번역되었다고 말하는 이유는, 이 문제는 원래 영문으로 된 문제입니다 (출처가 미국 정보 올림피아드).

그럼에도 전혀 번역되었다고 생각하지 못할 법한 내용으로 재밌게 번역되어 문제를 풀기에도 즐거웠네요.

 

문제를 자세히 읽어보면, 다음과 같이 요약할 수 있습니다.

• 정해진 노드가 입력으로 주어진다.
• 이미 건설된 노드 간의 엣지가 입력으로 주어진다.
• 노드 사이의 엣지를 최소로 건설하여 모든 노드가 연결되도록 하고, 이때 추가로 건설한 엣지의 거리의 총합을 구하여라.

문제 분류에 보면 최소 스패닝 트리 (MST; Minimum Spanning Tree)라고 되어 있습니다.

MST에 대한 이론적 설명은 여기를 참고하세요.

또, MST를 구현하는 방법으로는 대표적으로 Kruskal 알고리즘과 Prim 알고리즘이 있습니다.

Kruskal algorithm에 대한 이론적 설명은 여기를 참고하세요.

 

저는 kruskal 알고리즘을 이용하여 문제를 풀었습니다.

익숙하지 않은 MST 관련 문제라서 찾아보고 도움받은 부분이 많아,

코드를 작성하며 주석을 달아 이해하기 쉽도록 하였습니다.