5684. [Professional] 운동

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRxnnah2sDFAUo&categoryId=AWXRxnnah2sDFAUo&categoryType=CODE

SW Expert Academy

사실 완전탐색을 해도될지 굉장히 고민이 많이됬던 문제다.

 

그럼에도 불구하고 N값이 400까지인 제한조건과,

자기자신으로 돌아가는 경우가 존재하기에 BFS방식을 통한 완전탐색으로 문제를 풀었다.

사실 제일 좋은 방법은 Dijkstra방식을 통해, 각 지점에서 모든 다익스트라를 구하는것 아닐까 싶지만,

들어오는 도시간 거리가 정형적이지 않기때문에 BFS에 특정조건 하나를 추가해서 하는 방식으로 구현했다.