문제

상근이의 여행

풀이

해당 문제는 BFS로 접근하였다. 모든 여행지가 전부 이어져 있기 때문에 BFS 로 가는 것이 가장 최선이었다
그렇지만 그래프의 성격만 잘 파악해도 바로 풀 수 있는 문제였다
문제에서 원하는 것은 모든 여행지를 전부 가려고 하는 가장 작은 환승 수인데
여행지를 전부 가기 위해서는 최소 스패닝 간선을 가질때 이다 그 연산은 n - 1 로 한줄로 끝낼 수 있는 문제이다 ㄷㄷㄷㄷ

전체 코드

전체 코드

Reference

• https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html