🛣️ 최소 신장 트리
모든 마을을 잇는
가장 짧은 도로망은?
마을 여러 개를 전부 도로로 연결하고 싶은데, 도로 만드는 비용은 최소로 아끼고 싶어요. 어느 마을끼리 도로를 놓아야 "전체가 다 연결되면서 총 길이는 최소"가 될까요? 캔버스를 클릭해서 마을을 놓고 직접 확인해보세요.
크루스칼 알고리즘: 가능한 모든 도로(마을 쌍)를 짧은 순서대로 하나씩 검토해요. 이미 연결된 두 마을을 또 잇는 도로(원을 만드는 도로)는 버리고, 아직 안 이어진 마을을 잇는 도로만 채택해요. 이렇게만 해도 항상 최적의 답이 나온다는 게 증명되어 있어요!
채택된 도로 (최소 신장 트리)
검토했지만 버려진 도로 (원이 생겨서)
마을 수 0
도로 총 길이 0
모든 쌍을 다 이었다면 0
캔버스를 클릭해서 마을(점)을 5개 이상 놓아보세요.
🛣️ 최소 신장 트리 퀴즈
문제 1/3 · 정답 0개