목록크루스칼 (1)

전자공학 및 알고리즘

백준 14950 - 정복자(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제였습니다! 1번 도시는 정복하고 있기에 1번에서 최소 비용으로 갈 수 있는 곳을 먼저 정복한 뒤 Union+Find를 해주면 되는 문제였습니다! 문제 접근 방법 1. 백터에 시작점과 끝점, 비용을 저장한다. 2. 비용에 대해서 오름차순으로 정렬한다. 3. 1번 도시를 찾은 후, 먼저 연결해주고 시작한다. 4. Union+Find를 통해서 모..
백준 2021. 8. 16. 00:38
이전 Prev 1 Next 다음