[! 답변]Re:저좀 도와주세요(알바생구함)

[AlteRNativE]

질문을 보면서 즉흥적으로 써서 이거 뭐 틀린게 있을수도 있겠지만 잼나는 질문이라 답변씁니다.

먼저 질문내용을 살펴보니까 쓰시진 않았지만 가장빨리 갈수 있는 역을 표시하는거겠죠? 최단경로를 구해서 주어진 노선도에 이미지를 찍어야 하는거군요.

최단경로를 어떻게 구할수 있을까가 이문제의 주요한 사안같은데요. 전 그 최단경로에 대한 의문을 가지고 답변형(?)질문을 해봅니다.

.
.
.


각역은 1부터n(지하철역의 수)까지 운행시간이 있으면 되는데 그게 2분이라고 하셨으니까 하드코딩하믄 되겠고... 물론 어떤 역이 환승역이믄 7분이라니 이것도 하드코딩하믄 되겠군요.

그럼 이정도 제약(?)을 주면 이젠 출발역과 도착역 중간에 몇개의 환승역이 있고 환승역을 제외한 역은 몇개가 있냐.. 고거만 알면 구할려는시간은 나오네여

개괄적인 로직은 출발역과 도착역사이의 최단 경로를 루프를 돌리면서 돌릴때마다 환승역이면 환승역갯수를 카운트해서 올리고, 그냥역이면 그냥역갯수를 카운트해서 올려서 계산하면 답 나오겠네요.

히히 정말 간단한 생각이죠? 그치만 출발역과 도착역사이의 최단경로는 어떻게 뽑을까요?

지하철 노선도를 자세히 보면 트리로 보이나여? (안보여도 보이도록 상상의 나래를....) 그럼 가상의 출발지를 엄지와 검지를 이용해 짚어봅니다. 아마 그 출발점을 짚어서 약간만 올리면 그 출발지는 트리의 루트가 되고 옆의 인접한 다음역들은 차수가 2차인 노드가 되어 내려가겠지요...

이젠 트리로 보이지요?
그럼 기존에 있던 이진트리탐색법을 이용해 탐색을 하면 될것 같지 않나여? 이진트리탐색 알고리즘은 몇가지 있는데여 책보고 이해하셔야만 하는문제고요 이해하셨다면 아마 C나 C++로 구현된 알고리즘 찾아보면 많이 나올꺼에요.

그런담에 asp로 알고리즘을 바꿔보세요.
확실한 이해가 필수겠다 싶네요. 디비구성도 알고리즘에 맞게 구성하셔야 할듯한데...

.
.
.

글쓰면서 지금 생각해 보니 이게 더 복잡할듯도 싶푸네요... 디비까지 생각해 보니 머리 뽀개지네여.

참, 디직스트라 알고리즘이라고 있는데 최단경로알고리즘이라고 해서 유명한데 저도 글로는 표현이 한없이 길어지거나 내공이 한없이 없기때문에 이렇게밖에 도움을 못드릴듯해요...

.
.
.

또 다른 좋은 방법이나 보완해야할 점.. 리플주셨음 좋겠네요...