[백준 13418] 학교 탐방하기 - c++로 구현한 최소 스패닝 트리
문제 개요문제 번호: 13418제목: 학교 탐방하기난이도: 골드 3링크: 백준 13418번문제 설명학교안에 있는 모든 건물에 대한 이동 경로를 짜는 코드를 작성해야한다.최소한의 길을 선택해 모든 건물을 방문해야한다.길의 종류: 오르막길과 ( 0 ) 내리막길 ( 1 )입구 번호는 0번오르막길을 K번 오르면 피로도는 K^2피로도 계산은 최초 계산될 때 한번만 반영건물의 갯수: N (1 도로의 갯수: M (1 A 건물에서 B 건물까지 C (0은 오르막길 1은 내리막길)최악의 경로를 이용했을때 피로도와 최적의 경로를 이용했을때 피로도의 차이를 구해라접근 방법모든 건물을 방문하는 경로를 이어야하기 때문에 최소 스패닝 트리를 이용한다.간단하게 Union-Find를 이용한 크루스칼 알고리즘을 사용했다.이때 가중치는 ..
[백준 1647] 도시 분할 계획 - cpp로 구현한 최소 신장 트리
문제 개요문제 번호: 1647제목: 도시 분할 계획난이도: 골드 4링크: 백준 1647번문제 설명N개의 집이 있는데 연결되어있는 도로를 없애 N개의 집들을 2개의 마을 집단으로 분할해야한다.접근 방법도로를 지우는 것이 아닌 주어지는 M개의 도로에서 비용이 적은 도로를 선택한다.이때 마을1과 마을2는 서로 도로가 연결 되어 있으면 안된다. 즉 처음에 N개의 집을 각각의 집합으로 지정하고 도로를 연결할때 마다 집합을 합하여 2개의 집합으로 만들면 된다.이때 사용되는 알고리즘은 Union-Find를 이용한 크루스칼 알고리즘을 이용한다. 구현 코드#include#include#includeusing namespace std;int n, m;tuple edge[1000005];int p[100005];int fi..