백준 10021번 Watering the Fields

문제 설명

이번 문제는 여러 좌표에 농지가 있을 경우 이 농지들을 하나로 잇는 관개 시설을 만들 때, 모든 농지들을 포함하는 관개 시설을 짓는 비용의 최소값을 구하는 문제입니다.

좌표가 (ai,aj)인 농지 a와 (bi,bj)인 농지 b 사이의 관개 시설을 짓는 비용은 (ai-bi)^2+(aj-bj)^2 입니다.

 

문제 풀이

아이디어

트리

모든 농지를 잇는 최소의 비용을 구하기 위해서는 농지를 잇는 간선의 개수를 최소로 해야합니다. 그러므로, 농지를 잇는 간선의 개수는 {농지 개수-1}입니다.

 

정렬

관개 시설의 전체 비용의 최소값을 찾아야 하므로 비용이 가장 적은 간선부터 포함 여부를 확인해야합니다. 그러므로 비용을 기준 오름차순으로 간선을 정렬해야 합니다.

 

union-find

농지 a와 농지 b를 잇는 간선을 포함시킬지 여부를 확인하기 위해 농지 a와 농지 b가 같은 그래프 안에 있는지 확인해야 합니다.

a와 b가 같은 그래프에 있지 않다면 해당 간선을 포함시켜줍니다.

a와 b가 같은 그래프에 있다면, 해당 간선을 포함시킬 경우의 비용 합은 최소값이 될 수 없으므로 포함하지 않습니다.

 

풀이

비용 기준 정렬

각 노드의 간선들을 비용을 기준으로 정렬할 것이므로 heapq를 이용합니다.

각 노드의 간선 비용들을 계산하여 [{비용}, {노드1}, {노드2}]를 한 원소로 하여 heapq에 넣어줍니다.

 

작은 비용의 간선부터 결정

heapq에 들어있는 원소들을 하나씩 heappop해주어, 작은 비용의 간선부터 관개 시설에 포함할 것인지 결정합니다.

 

노드들간의 부모를 지정해주고 각 노드의 초기 부모는 자기 자신을 가리키도록 했습니다.

각 간선에 연결된 노드1과 노드2가 다른 부모를 가리킬 경우, 두 노드는 같은 그래프 상에 있지 않으므로 해당 간선을 관개 시설에 포함해줍니다.

또한, 작은 번호 노드의 부모가 높은 번호 노드의 부모를 가리키도록 설정했습니다.

 

각 간선에 연결된 노드1과 노드2가 같은 부모를 가리킬 경우, 두 노드는 이미 연결된 관개 시설이 존재하므로 해당 간선은 관개 시설에 포함하지 않습니다.

 

현재 포함된 간선의 개수가 노드개수-1이 될 때까지 반복합니다.

 

 

해결

이번 문제는 영어로 되어 있어 단어 하나(unless)를 놓쳐 조금 오래 걸렸던 문제입니다.

 

문제 링크 : https://www.acmicpc.net/problem/10021

10021번: Watering the Fields

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/10021.py