문제 설명동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.그렇..
문제 설명선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.https://www.acmicpc.net/problem/1368 제한 사항 풀이문제를 요약하면, N개의 논에 물을 모두 채우기 위한 최소 비용을 구해야 한다.논에 물을 채우는 방법은 두 가지이다.직접 물을 채우기다른 논에서 끌어오기두 방법은 비용이 다르다. 해당 문제는 문제의 표현을 살짝 바꿔보면 쉽게 풀 수 있다.물을 직접 채우는 방식이 없다..
문제 설명그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.https://www.acmicpc.net/problem/1197 제한 사항 풀이문제를 요약하면, 최소 스패닝 트리를 만들고 가중치를 출력하는 것이다.최소 스패닝 트리란, 그래프의 모든 노드를 포함하는 최소 가중치 트리를 말한다. 최소 스패닝 트리를 구하는 방법은 크게 두 가지이다.크루스칼 알고리즘프림 알고리즘 해당 문제에서는 크루스칼 알고리즘을 사용하였다.크루스칼 알고리즘은 간선 리스트를 통해 최소 스패닝 트리에 포함되는 노드를 확장하는 방법이다.우선, 간선리스트의 가중치를 ..
문제 설명Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 (xi - xj)^2 + (yi - yj)^2FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow a sequence of pipes to reach any other ..
