[boj] 백준 1647

[블로그 이전]

2023.03.06

 

https://www.acmicpc.net/problem/1647

정말 정말 안 쓰던 알고리즘을 쓰는 문제이다.

괜히 오기생겨서 어제부터 풀다가 어제는 중간에 포기하고 실버 풀어버림 ㅋㅋㅋㅋㅋ

하.지.만

오늘 해냈다는 사실! ㅎ

​

그래프를 만들고 mst 사용하는 문제

​

일단 그래프는 priority_queue로 해결

​

mst 만드는 방법이 2개가 있다.

1. 크루스칼
2. 프림

​

나는 크루스칼을 썼다.

간선 queue를 cost 기준으로 queue에 넣어준 후 하나씩 빼면서 from과 to의 parent가 다른지 확인한다.

다르면 cost를 더해서 최종 비용 만을 구한다.

​

마을을 두 개로 나눈다고 했으니까 마지막으로 최소 비용이 되려면 도로 중 가장 비싼거를 없애면 끝!