문제 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를 구했기 때문에 가장 마지막에 연결된 간선을 지워주..

문제 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)을 활용해 풀이하면 된다. 해시맵은 형으로 선언하여 이름과 이름에 대한 번호를 대응시킨다. 이름을 입력받을 때마다 해시맵에 없다면 새로운 번호를 할당한다. 이 번호는 유니온 파인드에서 각 노드의 루트 노드가 된다. 유니온 파인드에서는 루트 노드를 저장하는 배열과 해당 그룹에 속한 친구들의 수를 저장하는 배열을 같이 이용한다. 합집합 연산을 통해 루트 노드를 변경해주고 그에 따라 ..

문제 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드(Union-Find)를 활용한 문제다. 도시들의 연결 정보를 입력받아 합집합(Union) 연산을 수행하고 여행 계획에 포함되어 있는 도시들이 합집합인지 아닌지 판별하여 결과를 출력하면 된다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() var st : StringTokenizer val ..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 것으로 크루스칼 알고리즘을 사용한다. 신장 트리란 주어진 그래프에서 일부 간선을 선택하여 모든 노드를 연결하되 싸이클이 없는 트리이다. 여러 신장 트리들 중에서 간선의 가중치의 합이 최소인 것이 최소 신장 트리이다. 최소 신장 트리를 구하는 방법인 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하기 위해 사용한다. 먼저 입력받은 그래프를 간선의 가중치를 기준으로 오름차순 정렬한다. 그 후, 가중치가 가장 낮은 간선부터 선택하여 유니온 파인드(Union-..