밤이 블로그

BOJ#2887 행성 터널 * 문제https://www.acmicpc.net/problem/2887 * 풀이 MST, 최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 (문제에도 명시되어 있듯이) 행성이 N개 이므로, 간선은 N-1개가 됩니다. 이 문제를 풀 때 어려웠던 점은 간선 정보가 직접적으로 주어지지 않고직접 간선 정보를 만들어야 한다는 점입니다. 주의할 점으로는N이 최대 100,000 이므로 모든 간선을 입력하려면 100,000 * 100,000이 됩니다. (시간 초과) 따라서 모든 간선을 추가할 수 없으므로, 아래 방법대로 최소 간선만 추가해줍니다. 간선 비용은 문제에 주어진대로 min(x좌표 차이, y좌표 차이, z좌표 차이) 이므로1. x좌표를 기준으로 정렬 -> i-1 노드와 i 노..

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

BOJ#1197 최소 스패닝 트리 * 문제https://www.acmicpc.net/problem/1197 * 풀이 - MST(최소 스패닝 트리), 프림, 크루스칼 알고리즘, Union-Find 자료구조 설명http://stack07142.tistory.com/54 - MST (Minimum Spanning Tree)를 구하는 방법으로 아래 2가지 알고리즘이 있습니다.1) Prim's Algorithm, 프림2) Kruskal Algorithm, 크루스칼 1197번 문제를 위 2가지 알고리즘으로 풀어보았습니다. 1. Prim's Algorithm, 프림메모리 : 18848 KB, 시간 : 1244 MS import java.io.BufferedReader; import java.io.BufferedWri..