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 문제 풀이에 이용된 알고리즘: 크루스칼 알고리즘 주어진 그래프에서, 노드들을 연결하는 최단 거리 트리를 생성하는 문제이다. 즉, 최소 신장 트리 문제이며 크루스칼 알고리즘으로 간단히 풀 수 있다. 단, 간선을 입력 받을 때 "남초남초" 혹은 "여초여초"를 연결하는 간선은 애초에 크루스칼 알고리즘의 대상이 되는 간선 그룹에 포함시키지 않는다는 점..

문제 링크 : https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다. 개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다. 효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 ..