밤이 블로그

BOJ#13418 학교 탐방하기 * 문제https://www.acmicpc.net/problem/13418 * 풀이앞서 살펴봤던 최소 스패닝 트리 문제입니다. 1197번과 같은 기본 문제이고,(http://stack07142.tistory.com/53)크루스칼 알고리즘을 이용했습니다. 어려운 문제는 아닙니다만, 최소/최대 둘 다 구해야 하므로애초에 우선순위 큐를 2개 만들어서, 오름차순/내림차순으로 정렬할 수 있도록 했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2313418_SchoolTour

최소 스패닝 트리Prim(프림), Kruskal(크루스칼) 알고리즘+ Union-Find 자료구조 * 개요 - 신장 트리(스패닝 트리, Spanning Tree)란?1. 그래프의 모든 정점이 간선으로 연결되어 있다.2. 그래프 안에 사이클이 포함되어 있지 않다. - 최소 신장 트리(최소 스패닝 트리, Minimum Spanning Tree)란?말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리 - 프림과 크루스칼 알고리즘은 최소 스패닝 트리를 구하는 방법 중 하나이다.- 둘 다 Greedy Method을 기초로 하고 있다. (당장 눈앞의 최소 비용의 선택을 해서 결과적으로 최적의 Solution을 찾는다.) - 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘이다..