[백준] 최소신장트리 (MST) - 최소 스패닝 트리

지난번 최소신장트리의 개념을 공부했다.최소한의 개념만으로 풀어 볼 수 있는 문제가 바로 아래 링크의 문제이다.https://www.acmicpc.net/problem/1197 최소신장트리는 노드 , 간선 , 간선의 가중치가 주어지는 상황에서 최소한 간선의 가중치를 유지하며 모든 노드가 하나의 그래프에 속해있는 상태를 말한다.위 설명을 봤을때 딱 기억나는것이 한가지 있다. 바로 유니온 파인드..유니온 파인드를 이용하면 MST를 구성할 수 있다.유니온 파인드의 사이클을 점검하는 TASK, 같은 그래프에 속하는지 보는 TASK가 명확히 들어 맞는다.물론 유니온 파인드만 사용하면 풀순없지만 +@를 통해 쉽게 해결할 수있다.MST의 목표는 "최소의 간선 가중치"이다. 두 노드와 간선, 가중치가 주어질 것인데 이때..
카테고리 없음 2024. 11. 25. 18:58
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함