지하철 노선 최단 거리 찾기 알고리즘의 맹점

수학문제중에 최단거리 찾기 문제가 있고

실제로 알고리즘중에서도 최단거리와 관련된 알고리즘들이 있습니다.



지금은 너무 흔해져서 요즘 핸드폰에 부가기능으로 달려 있는 지하철 노선 최단거리 찾기.

프로그램이 뱉어내는 당신에게 알려주는 최단거리 얼마나 믿고 계십니까?


저도 개발자이지만 개발자 관점에서 보는 지하철 최단거리 찾기는 그냥 간단히 수식만으로는 풀리지 않습니다.

왜냐하면 환승이라는 강력한 걸림돌이 있기 때문입니다.

게다가 이 변수에 더해 지하철 배차간격까지 더해진다면

지하철 노선 최단거리가 내놓는 결과값과 실제값은 확연히 틀려집니다.




자 그럼 그 예를 한번 들어보겠습니다.

지하철 2호선 구로디지털단지역에서 3호선 동대입구역까지 가는 최단거리를

네이버지하철노선과 다음지하철노선 찾기 기능을 이용하여 테스트 해봅니다.

네이버 결과값

구로디지털단지 -> 교대(3호선 환승) -> 동대입구
소요시간 39분

다음 결과값
구로디지털단지 -> 을지로3가(3호선 환승) -> 동대입구
소요시간 평균 38분



실제로 두개의 노선을 비교하여 보면

평균적으로 다음에서 내놓은 결과값이 실제로도 더 잛습니다.

물론 그차이가 5분안밖의 차이이긴하지만

그 경로는 판이하게 다릅니다.


같은 최단거리 구하는 알고리즘임에도 불구하고

네이버와 다음의 지하철 노선 최단거리 검색결과가 다릅니다.



실제로 완벽한 지하철 노선 최단거리를 구하려면

지하철 열차 도착시간(평일과 토요일, 공휴일이 모두 다름)과 환승시 걸리는 평균적인 시간을 고려하여

지하철 최단거리 노선도가 나와야 하지만 현실적인 어려움이 있는 상황입니다.

특히나 몇몇역은 환승하기 위해 다른 호선으로가는 길이 너무 긴 역도 있습니다.




최단거리를 너무 맹신하지 말고 여러분의 경험을 믿으시길 바랍니다.