최소 스패닝 트리3 [백준] 13418: 학교 탐방하기 - JAVA https://www.acmicpc.net/problem/13418 풀이MST를 구해 오르막길의 개수를 찾는 문제였다. 오르막길을 가중치가 0, 내리막길은 1로 주어지는데 오르막길을 최대로 이용한 경우, 최소로 이용한 경우를 각각 구해야 한다. 오르막길의 가중치가 0이므로 가중치가 작은순으로 프림 알고리즘을 구현하면 최대로 이용한 개수를 구할 수 있고, PriorityQueue의 정렬 조건을 내림차순으로 해주면 오르막길을 최소로 이용한 개수를 구할 수 있다. 메모리: 191972KB시간: 1292ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int point; .. 2024. 5. 13. [백준] 1774: 우주신과의 교감 - JAVA https://www.acmicpc.net/problem/1774 풀이최소 신장 트리를 구하는 문제이다. 정점을 다 연결해야 하는데 이미 연결된 선이 주어진다. 이미 연결된 선은 가중치를 0으로 두고 계산했다. 크루스칼과 프림 알고리즘이 있는데 프림 알고리즘을 사용해봤다. 프림 알고리즘은 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 최소신장트리를 찾는 알고리즘이다 1. 임의 정점을 하나 선택해서 시작한다. 2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선과 연결된 정점을 선택한다. 3. 모든 정점이 선택될때까지(정점의 개수 - 1개의 간선이 선택될때까지) 1, 2번과정을 반복한다. pq에 방문하지 않은 점들을 넣고 가중치가 작은 순으로 PriorityQueue를 이.. 2024. 5. 13. [백준] 21924: 도시 건설 - JAVA https://www.acmicpc.net/problem/21924 풀이도로를 연결해야 한다. 최소한의 비용으로. 즉, 최소 스패닝 트리(MST)에 대한 문제이다. 크루스칼과 프림의 두 가지 알고리즘으로 풀 수 있는데 크루스칼 알고리즘을 선택했다. 크루스칼 알고리즘은 간선을 하나씩 선택해서 최소신장트리를 찾는 알고리즘이다. 1. 처음에 모든 간선을 가중치에 따라 오름차순으로 정렬하고 시작한다. 2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.(이때, 사이클이 존재하게 될 경우 다음으로 가중치가 낮은 간선을 선택한다.) 3. N-1개의 간선이 선택될때까지 2번 과정을 반복한다. 간선을 비용에 따라 정렬해야 하는데 정렬하는 방법으로 PriorityQueue를 이용했다. 크.. 2024. 5. 13. 이전 1 다음