문제 링크입니다: https://www.acmicpc.net/problem/10021
10021번: Watering the Fields
Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b
www.acmicpc.net
Union Find 자료구조를 통해 풀 수 있는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 각 좌표들 사이 간의 거리를 구하고 거리가 C 이상인 것을 우선 벡터에 집어 넣습니다.
2. 벡터를 거리 기준으로 오름차순 정렬한 뒤 모든 구간이 연결되었는지 여부를 Union Find를 통해 확인합니다. (정렬하는 이유는 구간의 합을 최소화시키기 위해)
2.1 벡터 내 거리들을 모두 merge를 했을 때 합쳐지지 않은 구간의 개수가 N - 1 미만일 경우 모든 파이프가 연결되어 있지 않은 것이기 때문에 -1을 출력하고 프로그램을 종료합니다.
2.2 합쳐지지 않은 구간의 개수가 N - 1 이상일 경우 모든 파이프가 연결되었기 때문에 여태까지의 구간의 합을 출력해주고 프로그램을 종료합니다.
개발환경:Visual Studio 2019
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 10090번 Counting Inversion (0) | 2020.07.26 |
|---|---|
| 백준 1264번 모음의 개수 (0) | 2020.07.19 |
| 백준 9655번 돌 게임, 백준 9659번 돌 게임 5 (0) | 2020.07.07 |
| 백준 19238번 스타트 택시 (4) | 2020.06.29 |
| 백준 19237번 어른 상어 (0) | 2020.06.25 |