문제 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 이 문제는 MST(최소 스패닝 트리)를 구하는 것로 이번에는 크루스칼 알고리즘을 사용해서 풀이했다. 우선순위 큐를 활용하여 비용이 낮은 순서대로 길을 선택하여 MST를 만들고 사이클이 발생하는 간선은 제외해준다. MST를 만드는 과정에서 발생하는 비용들은 더해준다. MST에서 간선을 하나 지우는 것으로 마을을 두 개로 나눌 수 있다. 우선 순위 큐를 이용해 MST를 구했기 때문에 가장 마지막에 연결된 간선을 지워주..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 이 문제의 풀이 과정과 사용한 알고리즘은 다음과 같다. 1. 섬에 고유 번호 부여 (DFS): 입력받은 지도를 DFS나 BFS를 이용하여 각 섬에 번호를 부여해준다. 입력에서 1이 섬이기 때문에 첫번째 섬부터 2번으로 부여해주었다. 2. 각 섬을 연결할 수 있는 방법 구하기 (BFS): 각 섬을 연결하는 가능한 모든 다리를 찾아준다. 길이가 1보다 큰 다리들을 거리에 따라 오름차순으로 정렬될 수 있게 우선 순위 큐에 저장한다. 3...

문제 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 크루스칼 알고리즘을 사용하였다. 문제는 최대로 절약할 수 있는 비용을 찾는 것이므로, 크루스칼 알고리즘으로 찾음 최소 스패닝 트리(MST)의 비용을 초기 비용에서 빼준 값을 출력하면 된다. 기본적인 유니온 파인드로는 시간 초과 문제가 발생하여 경로 압축을 적용한 유니온 파인드 구현이 필요하다. 경로압축은 파인드 함수에서 부모를 찾아가는 중간에 거치는 모든 노드들..

문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 크루스칼 알고리즘을 사용하였다. 문제는 각 정점의 위치가 주어지기 때문에, 정점들 간의 거리를 계산하여 간선의 정보를 리스트에 저장해준다. 그리고 나서 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 구하고 결과를 출력해준다. 코드 import java.util.* import kotlin.math.* // 별의 좌표를 저장..

문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 문제는 각 정점의 위치가 주어지기 때문에, 정점들 간의 거리를 계산하여 간선의 정보를 우선 순위 큐 리스트에 저장해준다. 그리고 나서 프림 알고리즘을 이용하여 최소 스패닝 트리를 구하고 결과를 출력해준다. 코드 import java.util.* import kotlin.math.* // 별의 좌표 정보를 저장하는 데이터 클래..