문제 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. 최소 간선 선택: 우선 순위 큐에서 ..

문제 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이 문제의 답은 모든 노드(국가)를 연결할 수 있는 간선(비행기)의 개수로 노드(국가)의 개수에서 1을 빼면 된다. 만약 문제가 최소 비행 횟수나 최단 거리를 찾는 것이었다면 입력받은 간선으로 그래프를 만들어야 했겠지만, 이 문제에서는 타야하는 비행기의 종류만 구하면 되기 때문에 간단히 노드 개수에서 1을 빼주면 된다. 코드 import java.util.* fun main() { val br = System.`in`..

문제 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 유니온 파인드(Union-Find)를 활용해 풀이하면 된다. 반복문을 통해 입력받은 선분을 합집한(Union) 연산하고 사이클이 발생한 경우에 해당 번호를 출력한다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() var st = StringTokenizer(br.readLine()) val num =..

문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 입력된 친구 관계를 해시맵과 유니온 파인드(Union-Find)을 활용해 풀이하면 된다. 해시맵은 형으로 선언하여 이름과 이름에 대한 번호를 대응시킨다. 이름을 입력받을 때마다 해시맵에 없다면 새로운 번호를 할당한다. 이 번호는 유니온 파인드에서 각 노드의 루트 노드가 된다. 유니온 파인드에서는 루트 노드를 저장하는 배열과 해당 그룹에 속한 친구들의 수를 저장하는 배열을 같이 이용한다. 합집합 연산을 통해 루트 노드를 변경해주고 그에 따라 ..