플로이드-와샬
-
[백준]29140: 가운데에서 만나기 - JAVA문제풀이/백준 2021. 7. 23. 15:13
[백준]29140: 가운데에서 만나기 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이 🪑 생각지도 못한 부분에서 헤멨던 문제였다..! 일단 문제를 보자마자 Shortest Path 문제라는 것을 알았고 다익스트라, 플로이드-와샬 알고리즘을 떠올렸다. 📝문제의 조건을 정리해 보자! 도시와 도시를 연결하는 간선은 유향(방향성을 가진다)이다. 왕복 시간은 A -> B -> A이다. 왕복 시간 중 최대가 최소가 되는 도시를 선택한다. 여러개인 경우 오름차순으로 출력한다. 🙋♀️ '최대가 최소'에서 이분탐색 힌트를 얻고 처음에는 이분탐색으로 접근하였다. 도시별로..