17940 - 지하철 📌 문제 대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다. 형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서의 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때 마다 환승 1회로 계산한다. 위의 그림에서 원은 지하철역을 의미하고 선들은 지하철역들이 연결되어 있는 지를 나타낸다. 흰색으로 표시된..
