BOJ 문제풀이/최소스패닝트리 (MST) 썸네일형 리스트형 백준 16398 : 행성 연결 https://www.acmicpc.net/problem/16398 Kruskal 알고리즘과 UnionFind에 대한 개념을 알고있으면 쉽게 풀수 있는 문제였다.(물론 학교 시험때는 못풀었지만..) 수업때 최소비용신장트리(MST) 개념에 대해 배웟는데몇일만 더 빨리 배웠었으면.. 아무튼 간단하게 요약하자면MST 란 그래프의 노드를 간선으로 연결함에 있어 각 간선마다 다른 비용이 든다.이때 그 비용을 최소화 시켜야 한다. 1. 간선 연결은 spanning tree 구조이다. -> 즉 n개의 노드가 있으면 간선(edge)은 n-1개로 모든 노드를 연결 시켜야 하며 -> 이때 n-1개로 구성한 노드는 Cycle이 돌지 않아야 한다. MST를 풀기 위한 대표적인 알고리즘은 Kruskal 과 Prim이 있는데이문.. 더보기 이전 1 2 다음