[백준 13418] 학교 탐방하기 - c++로 구현한 최소 스패닝 트리
문제 개요문제 번호: 13418제목: 학교 탐방하기난이도: 골드 3링크: 백준 13418번문제 설명학교안에 있는 모든 건물에 대한 이동 경로를 짜는 코드를 작성해야한다.최소한의 길을 선택해 모든 건물을 방문해야한다.길의 종류: 오르막길과 ( 0 ) 내리막길 ( 1 )입구 번호는 0번오르막길을 K번 오르면 피로도는 K^2피로도 계산은 최초 계산될 때 한번만 반영건물의 갯수: N (1 도로의 갯수: M (1 A 건물에서 B 건물까지 C (0은 오르막길 1은 내리막길)최악의 경로를 이용했을때 피로도와 최적의 경로를 이용했을때 피로도의 차이를 구해라접근 방법모든 건물을 방문하는 경로를 이어야하기 때문에 최소 스패닝 트리를 이용한다.간단하게 Union-Find를 이용한 크루스칼 알고리즘을 사용했다.이때 가중치는 ..
알고리즘
2024. 10. 18. 10:58