백준 2887 - 행성 터널 (파이썬)
각 축별로 정렬을 한뒤에 거리를 구하면 i노드인 경우에 i + 1노드가 가장 최소거리에 있는 연결점인걸 알 수 있습니다. 즉 i + 2부터는 거리를 구할 필요가 없어져 간선의 수가 줄어듭니다. 이렇게 구한 간선들을 크루스칼 알고리즘을 사용해서 마저 연결했습니다.
Recent Posts
백준 1774 - 우주신과의 교감 (파이썬)
미리 연결된 좌표들은 먼저 유니온 연산을 했고 연결되지 않은 좌표들은 크루스칼 알고리즘을 사용했습니다.
백준 17472 - 다리 만들기 2 (파이썬)
이번 문제는 개인적으로 굉장히 어려웠던 문제였습니다. 문제는 다음과 같은 순서로 해결했습니다.
백준 4386 - 별자리 만들기 (파이썬)
좌표끼리의 거리를 계산하고 크루스칼 알고리즘을 사용해 해결했습니다.
백준 1197 - 최소 스패닝 트리 (파이썬)
tree 배열에 입력을 받은 뒤 Kruskal’s algorithm을 사용했습니다. Kruskal’s algorithm은 간선을 기준으로 오름차순 정렬을 한뒤 가중치가 낮은 간선부터 차례로 연결을 해주는 알고리즘입니다.