반응형 mst2 [ 알고리즘 ] 코딩 - 백준 1647 - 도시분할계획.java 문제 링크 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net * 백준 - (자바)도시분할계획 - MST(최소 스패닝 트리) * 한 마을을 2개의 구역으로 나눈다. N개의 집과 M개의 길이 있다. 길은 양방향. 각 분리된 마을은 마을 * 안에서 집들이 서로 연결이 되어있어야 한다. 필요없는 길을 모두 없애고 남은 최소의 길의 유지비를 구하자. * 정점10만개. 길 100만개.. * 문제만 보고 마을을 나누고~.. 2021. 1. 8. [ 알고리즘 ] 코딩 백준 2887 - 행성 터널.java 백준 2887 - 행성터널 * 자바로 구현 * 행성의 위치는 x,y,z 의 좌표로 주어짐. * 행성간 터널을 뚫는데, A(x1,y1,z1) - B(x2,y2,z2)가 주어지고 * min(|x1-x2|,|y1-y2|,|z1-z2|)를 구하면 된다. * 예를들어 A(1,2,3) B(10, 2, 32) 인 경우에는 y좌표가 같으므로 비용은 0이 된다. * 행성 10만개.. 좌표값 -10^9 ~ + 10^9 * X좌표를 기준으로 정렬하고 Edge 추가 * Y좌표를 기준으로 정렬하고 Edge 추가 * Z좌표를 기준으로 정렬하고 Edge 추가 * 모든 Edge를 가중치를 기준으로 오름차순 정렬 * 정렬 된 Edge에 대해서 Kruskal 적용 public class BOJ_2887_Planet_Tunnel { .. 2020. 9. 5. 이전 1 다음 반응형
