문제 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.* // 별의 좌표 정보를 저장하는 데이터 클래..

문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 프림 알고리즘의 주요 단계는 다음과 같다. 1. 노드 선택: 임의의 노드를 선택하여 시작한다. 2. 우선 순위 큐 생성: 선택한 노드와 연결된 모든 간선을 우선 순위 큐에 추가한다. 이때, 간선의 가중치를 기준으로 오름 차순 정렬된다. 3. 최소 간선 선택: 우선 순위 큐에서 ..