Gi-Log

문제: SW Expert Academy 1251 하나로 "섬이나 도시, 컴퓨터 등등 어떤 정점들을 모두 잇는 최소 경로가 필요하다!"라는 문제가 나오면 십중팔구 최소 신장 트리(MST) 문제이다. 이 문제 또한 크루스칼 알고리즘을 적용하여 MST를 생성해서 풀 수 있는 문제였다. 본 블로그에서 몇 번 설명을 진행한 풀이가 있는데, 크루스칼 알고리즘을 간단히 설명하면 다음과 같다. 1. 어떤 노드들을 잇는 간선들을, 그 비용을 기준으로 오름차순 정렬한다. 2. 가장 비용이 적은 간선부터 연결을 시작한다. 3. 이 때, 간선을 연결했을 때 싸이클이 발생하게 된다면 해당 간선은 연결하지 않고 건너 뛴다. 위 알고리즘 구현을 위해서는 간선 정보를 어떤 컨테이너에 잘 담고, 정렬할 수 있어야한다. 그리고 싸이클 ..

문제 링크: https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 크루스칼 알고리즘 주어진 그래프에서, 노드들을 연결하는 최단 거리 트리를 생성하는 문제이다. 즉, 최소 신장 트리 문제이며 크루스칼 알고리즘으로 간단히 풀 수 있다. 단, 간선을 입력 받을 때 "남초남초" 혹은 "여초여초"를 연결하는 간선은 애초에 크루스칼 알고리즘의 대상이 되는 간선 그룹에 포함시키지 않는다는 점..