반응형
문제
https://www.acmicpc.net/problem/1774
1774번: 우주신과의 교감
(1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼
www.acmicpc.net
풀이
MST를 구하기 위해 크루스칼 알고리즘으로 풀이할 수 있는 문제입니다.
모든 우주신의 좌표와 좌표사이의 거리를 직접 구해주어야 합니다.
즉, 노드간의 간선을 구해주어야 합니다.
그 이후 통로의 개수는 합집합 연산을 통해 미리 합쳐주고,
간선의 비용을 오름차순으로 정렬을 하고, 사이클이 이루어지지 않는다면 이어줍시다.
그렇다면 최소 비용을 구할 수 있습니다.
소스코드
후기
좌표평면에서 MST를 만드는 문제였습니다.
MST를 구하는 알고리즘에 대해 알고있다면 어렵지 않게 풀 수 있는 문제입니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 17472 다리 만들기 2 (Swift) (0) | 2023.05.18 |
|---|---|
| [BOJ] 백준 6497 전력난 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 4386 별자리 만들기 (Swift) (1) | 2023.05.17 |
| [BOJ] 백준 1197 최소 스패닝 트리 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 9372 상근이의 여행 (Swift) (0) | 2023.05.16 |
