1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다. 최소신장 트리를 만드는 방법은 여러가지가 있다. ​ 1. 크루스칼 알고리즘 1) 모든 간선들을 오름차순으로 정렬한다. 2) 가중치가 작은 간선부터 하나씩 연결한다. 3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다. 4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다. ​ https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F 18. 크루스칼 알고리즘(Kruskal Algorithm) 이번 시간에 다루어 볼 내용은 바로 크루스..