[Java / 자바] 알고리즘 - 지하철 노드 탐색 (연결리스트, 트리 탐색 응용)

개발 노트/Java  2015.06.20 02:02

안녕하세요. 명월입니다. 이번 포스트는 지하철 노드 탐색에 대해서 작성해 보겠습니다.


사실 알고리즘에는 지하철 노드 탐색이라는 알고리즘은 없습니다. (혹시 있는데 제가 모를 수도 있습니다..) 비슷한 알고리즘은 있을 거라고는 생각되지만, 현재로써는 모르겠네요.


갑자기 이걸 왜 만드는가 하는 거에 대해서 회사 퇴근길에 문득 지하철 노선표를 보다가 이걸 탐색하는 알고리즘을 만들어 볼까는 생각이 들었습니다. 하나의 지하철 노선은 연결리스트라고 했을 때 환승역에서는 트리구조로 되어있는 탐색입니다.


쉽게 생각하면 연결리스트 + 트리구조라고 생각됩니다.


실제로는 이런 알고리즘을 쓰지 않고 모든 걸 데이터베이스로 처리할 겁니다. 검색할 때마다 알고리즘 구동시키면 엄청나게 느릴 테니깐요..
그래도 재미로 한 번 작성해보고 싶다는 생각해 만들어 봤습니다.


구성은 예외처리를 빼고 역정보를 가지고 있는 클래스(노드)와 노선 클래스로 구성되겠습니다.
노드는 연결리스트를 응용한 것으로 전 역과 다음 역에 대한 포인터를 가지고 노선 클래스에서 탐색하는 것입니다.



역 클래스에는 전역과 다음 역이 동대문 같은 경우는 여러 개의 노선이 중첩되어 있으니 ArrayList로 복수가 됩니다. 그 외에 역 코드, 역 이름 정보가 있습니다.


다음은 노선 탐색 클래스입니다.



기본적으로 연결리스트를 만들거나 파일을 읽어드려서 메모리상의 노선도를 만드는 함수 등이 있습니다.
그러나 이 클래스의 핵심은 search 함수와 nodeExplorer 함수입니다.
search 함수는 외수에서 어느역에서 어느역까지 검색을 할 것인가에 대한 호출이고 nodeExplorer 는 실제 노드 탐색이 이루어집니다.
출발역에서 한 역씩 이동할 때마다 검색을 하네요. 그리고 그 역에 대한 정보는 Stack으로 저장을 하고요. 왔던 역을 다시 들리게 되면 그건 잘 못 온 노선으로 그냥 pass합니다.


그리고 text 파일을 만들어서 데이터를 넣고 검색을 해 보겠습니다.



위 파일 정보는 지하철 역입니다.


위 정보는 연결 리스트 정보입니다.
그럼 Main을 작성해서 실행해 보도록 하겠습니다.



그럼 의정부역에서 교대역까지 검색해서 확인해 보겠습니다..


아래는 결과 내용입니다.



처리 시간이 상당히 걸리네요..
실제로 인터넷이나 모바일로 보는 노선 탐색은 이런 알고리즘을 작성하는 것이 아니라 데이터베이스를 기반으로 정보를 취득해서 표시할 겁니다.
뭐 처음 데이터를 만들 때는 이런 알고리즘을 이용했을지도 모르겠습니다.


소스 - github 바로가기


댓글 4개가 달렸습니다.
댓글쓰기

  1. 2015.06.23 21:54 |  수정/삭제  댓글쓰기

    비밀댓글입니다

    • 明月 v명월v
      2015.06.24 21:13 신고 |  수정/삭제

      안녕하세요... 블로그 방문 감사합니다...
      먼저 피보나치 힙 기반의 dijkstra는 뭔가요?? 첨듣는 알고리즘인데??
      피보나치는 수열의 명칭아닌가요?? 힙은 메모리의 논리적 기반이구요..
      dijkstra는 데이크스트라를 말씀하시는 건지?? 제가 만든 지하철 최단 경로와 데이크스트라 알고리즘이랑은 개념이 틀린 이야기 입니다만...
      데이크스트라는 각 도로의 길이를 설정해서 최단경로를 찾는 문제라고 기억을 하고 있습니다만.. 제가 만든건 모든 경로는 같은 길이라는 가정(실제로 지하철의 역간격읜 거의 비슷합니다. 3호선 빼고) 하에 노드를 가정 적게 거치는 경로, 즉 역을 가장 적게 지나치는 경로를 탐색해서 최단거리를 찾는 알고리즘입니다.
      모든 노드를 연결 리스트로 묶고 재귀함수를 이용한 트리 탐색으로 갈 수 있는 모든 경로를 구한 다음에 가장 적은 노드 수를 가진 것을 출력하는 방식입니다.
      핸드폰으로 보는 노선 탐색은 이런 알고리즘을 작성하는 것이 아니라 데이터베이스를 기반으로 정보를 취득해서 표시합니다" 에 대해서는 실제로 우리가 핸드폰이나 인터넷으로 지하철 시간표 및 걸리는 시간, 최단 거리를 나타내는 프로그램들은 이런 알고리즘을 사용해서 나타내는 것 이 아닌 종로에서 출발하면 모든 역의 최단 거리를 데이터 베이스에 집어넣고 검색하는 방식으로 개발합니다.
      이유는 성능 때문이겠지요... 알고리즘을 일일히 돌려 버리면 느려져 버리니깐요.... 도움이 되시길 바랍니다.

    • 明月 v명월v
      2015.06.24 21:15 신고 |  수정/삭제

      제가 예제 소스를 첨부하였으니 실제로 돌려 보시면 이해하시는데 도움이 되실 수 있습니다.

    • skin0011
      2016.04.24 14:39 신고 |  수정/삭제

      NullPointerException이 뜨네요...
      java.lang.NullPointerException
      at Subway.setNextStation(Subway.java:101)
      at Subway.setNextStation(Subway.java:107)
      at Subway.setLinkStation(Subway.java:90)
      at SubwayFind_2605_2615.main(SubwayFind_2605_2615.java:14)