반응형
문제
https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
풀이
좌표 평면에서 MST를 만드는 문제입니다.
간선이 주어지지 않았기 때문에 직접 간선을 구해주어야 합니다.
두 별 사이의 모든 거리를 구해주어야 합니다.
프로퍼티로는 시작노드, 도착노드, 비용을 갖는 Edge 구조체를 선언해주었습니다.
두 별 사이의 모든 거리를 구해주고, 구조체 배열에 넣어줍시다.
이제 크루스칼 알고리즘을 사용하여 최소 비용을 구할 수 있습니다.
거리를 기준으로 오름차순으로 정렬한 후, 사이클을 이루지 않는다면 이어주고 비용을 누적해서 더해줍시다.
누적된 비용이 답이 됩니다.
소스코드
후기
문제에서 간선이 주어지지 않았기에 직접 간선을 만들어줘야 했던 문제였습니다.
접근만 한다면 어렵지 않게 풀 수 있는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 6497 전력난 (Swift) (0) | 2023.05.18 |
|---|---|
| [BOJ] 백준 1774 우주신과의 교감 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 1197 최소 스패닝 트리 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 9372 상근이의 여행 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 20040 사이클 게임 (Swift) (0) | 2023.05.16 |
