2025학년도 자료구조 및 알고리즘 팀 프로젝트로, 서울 지하철 1~5호선의 최적 경로를 찾는 시스템을 구현했습니다. 사용자는 최단 시간 또는 최소 환승 두 가지 기준 중 하나를 선택하여 경로를 탐색할 수 있습니다.
· 곽용진 : Floyd-Warshall 알고리즘, Y자 환승 구간 최적화, Folium을 이용한 맵 시각화 · 김이영 : 데이터 수집 및 전처리, Dijkstra 알고리즘, 최소 환승 Dijkstra 알고리즘
· 최단 시간 경로 탐색: Dijkstra 알고리즘을 사용하여 출발지부터 도착지까지 가장 빠르게 도착할 수 있는 경로를 제공합니다.
· 최소 환승 경로 탐색: 환승을 최소화하는 경로를 우선적으로 탐색하는 변형된 Dijkstra 알고리즘을 구현하여, 환승을 꺼리는 사용자에게 최적의 대안을 제공합니다
· Y자 분기 환승 최적화: 금천구청, 병점, 구로, 강동역과 같이 동일 역, 동일 호선 내에서 반대 방향으로 갈아타야 하는 특수한 'Y자 환승' 구간을 탐지하고 경로를 최적화하는 독자적인 로직(y_clear)을 구현했습니다.
· 이중 모드 지원 (Dijkstra & Floyd-Warshall): 단일 경로 탐색에는 Dijkstra를, 반복적인 다중 경로 탐색 시에는 사전 계산된 Floyd-Warshall 결과를 활용하여 O(1) 수준의 빠른 응답이 가능하도록 설계했습니다.
· 경로 시각화: folium 라이브러리를 사용해 탐색된 경로를 지도 위에 시각적으로 표시합니다. 각 호선은 고유한 색상으로 구분되며, 환승 지점과 이동 경로를 직관적으로 파악할 수 있습니다.
총 12개의 공공 데이터를 수집하여 시스템에 필요한 형태로 가공했습니다.
· 서울교통공사: 노선별 지하철역 정보, 역사 좌표(위/경도), 환승 정보, 표정속도 정보 · 국가철도공단: 1~5호선 역간 거리 정보
- 각 역의 좌표, 호선, 연결 정보를 통합하고 '역명_호선' 형식의 고유 노드를 생성했습니다.
- 역간 거리와 호선별 표정속도를 이용해 이동 소요 시간(가중치)을 계산했습니다.
- 환승 정보를 정제하여 (역명,호선):소요시간 형식으로 통일했습니다.
- 누락된 역 정보를 보완하고, 불필요한 중복 데이터를 제거하여 최종적으로 input2.csv 파일을 생성했습니다.
graph TD
A[START] --> B{데이터 로드};
B --> C{데이터 전처리};
C --> D{그래프 생성};
D --> E{사용자 입력: 출발/도착역};
E --> F{경로 탐색 알고리즘 선택};
F --> G[1. 최단 시간 (Dijkstra)];
F --> H[2. 최소 환승 (Modified Dijkstra)];
F --> I[3. 모든 경로 사전계산 (Floyd-Warshall)];
subgraph "탐색 결과"
G --> J{경로 복원};
H --> J;
I --> J;
end
J --> K{Y자 환승 최적화};
K --> L[경로 출력 (텍스트)];
K --> M[경로 시각화 (Folium)];
L --> Z[END];
M --> Z;
- 필요한 라이브러리를 설치합니다.
pip install pandas folium numpy matplotlib- 지하철_최단경로.ipynb 파일을 시행하여 출발역과 도착역 정보를 입력합니다.
# 사용자로부터 입력받는 부분
start_node = get_valid_node("출발 역과 호선을 입력해주세요 (예: 서울역 1): ", nodes)
end_node = get_valid_node("도착 역과 호선을 입력해주세요 (예: 강남역 2): ", nodes)입력: 출발: 서울역 1, 도착: 강남역 2
출력(텍스트)
-----------------최단경로-----------------
총 소요 시간: 25분
-------------------출발-------------------
0초
서울역(1호선)
[1호선에서 4호선으로 환승] : 2분 12초
------------------------------------------
13분
서울역(4호선) → 숙대입구역(4호선) → ... → 사당역(4호선)
[4호선에서 2호선으로 환승] : 1분
------------------------------------------
8분 48초
사당역(2호선) → 방배역(2호선) → ... → 강남역(2호선)
-------------------도착-------------------
환승 횟수 : 2
-----------------최소환승-----------------
최소 환승 경로 소요 시간: 40분 24초
-------------------출발-------------------
2분
서울역(1호선) → 시청역(1호선)
[1호선에서 2호선으로 환승] : 1분 24초
------------------------------------------
37분
시청역(2호선) → 을지로입구역(2호선) → ... → 강남역(2호선)
-------------------도착-------------------
환승 횟수 : 1
출력 (지도 시각화)
최단 경로 탐색 결과가 Folium 지도로 시각화되어, 각기 다른 색상으로 표시된 호선을 따라 경로를 쉽게 확인할 수 있습니다.
| 알고리즘 | 실행 시간 (단일 쿼리) | 비고 |
|---|---|---|
| Dijkstra | 약 0.001s | 단일 경로 실시간 탐색에 유리 |
| Floyd-Warshall (최초 계산) | 약 4.0s ~ 8.5s | 모든 경로를 사전 계산 |
| Floyd-Warshall (결과 재사용) | 약 0.0002s | 사전 계산된 파일 로드 후 O(1) 탐색 |
| · Dijkstra는 단일 쿼리에 대해 매우 빠르고 메모리 효율적입니다. | ||
| · Floyd-Warshall은 초기 계산 비용이 크지만, 결과를 저장하고 재사용하면 반복적인 쿼리에서 훨씬 빠른 성능을 보입니다. |
· Y자 분기 환승을 위해 새로운 가상의 역을 추가하였습니다.
· 이후 경로 복원을 통해 가상의 역에 사용된 시간을 활용하는 경우와 그렇지 않는 경우를 나누어 처리하였습니다.
- OpenAI GPT (ChatGPT) · 코딩 도움, 아이디어 정리 및 문서 작성 과정에서 사용하였습니다.
- 라이브러리 공식 문서 · folium : https://python-visualization.github.io/folium/latest/ · matplotlib : https://matplotlib.org/stable/index.html · numpy : https://numpy.org/doc/ · pandas : https://pandas.pydata.org/docs/
자료구조와 알고리즘 공부를 하며 마주했던 그래프, 최단 경로, 우선순위 큐와 같은 개념들은 늘 흥미로운 이론의 영역에 머물러 있었습니다. 하지만 이번 '서울 지하철 최적 경로 탐색기' 프로젝트를 통해, 책에서만 보던 그 이론들이 어떻게 현실 세계의 문제를 해결하는 강력한 도구가 될 수 있는지 몸소 체험하며 한 단계 성장할 수 있었습니다.
프로젝트를 시작하며 마주한 첫 번째 벽은 화려한 알고리즘이 아닌, 바로 '데이터' 그 자체였습니다. 서울시와 국가철도공단 등 여러 곳에 흩어져 있는 12개의 지하철 관련 파일은 제각기 다른 형식과 인코딩, 불필요한 정보를 담고 있었습니다. 누락된 위경도 좌표, 제각각인 역간 거리 표기 등 현실의 데이터는 결코 책이나 온라인 저지 사이트처럼 깔끔하지 않았습니다. 이 데이터들을 하나의 정제된 input2.csv 파일로 통합하는 과정은, 알고리즘 구현만큼이나 중요하고 많은 노력이 필요한 작업이라는 것을 깨닫게 해주었습니다.
데이터라는 산을 넘자, 비로소 이론을 현실에 적용하는 단계에 이르렀습니다. 단순히 Dijkstra 알고리즘을 구현하는 것을 넘어, **'어떤 경로가 진정으로 최적의 경로인가?'**라는 질문을 스스로에게 던졌습니다. 그 결과 '최단 시간'을 위한 Dijkstra와 '최소 환승'을 위한 변형된 Dijkstra를 모두 구현하게 되었습니다.
특히 사용자가 많아 반복적인 요청이 들어올 상황을 가정하여, 초기 계산 비용은 높지만 이후 O(1)에 가까운 속도로 응답할 수 있는 Floyd-Warshall 알고리즘까지 구현하고 그 결과를 저장하여 재사용하는 방식을 설계했습니다. 이 과정에서 각 알고리즘의 시간 복잡도와 공간 복잡도가 실제 성능에 어떤 영향을 미치는지, 어떤 상황에 어떤 알고리즘을 선택해야 하는지에 대한 깊이 있는 고민을 할 수 있었습니다.
이번 프로젝트에서 가장 큰 성취감을 느꼈던 부분은 'Y자 분기 환승' 문제를 해결한 것입니다. 금천구청역이나 강동역처럼, 같은 역, 같은 호선임에도 불구하고 특정 방향으로 가기 위해 반대편 승강장으로 이동해야 하는 복잡한 예외 상황이었습니다. 이 문제를 해결하기 위해 가상의 노드를 만들고, 경로 탐색 후 해당 구간을 지나는지 판별하여 시간을 최적화하는 y_clear 함수를 독자적으로 설계했습니다. 모두가 흔히 알고 있는, 알려진 알고리즘이 아닌 나만의 창의적인 방법으로 풀어냈을 때의 기쁨은 이루 말할 수 없었습니다.
이번 프로젝트를 통해 이론을 현실에 성공적으로 적용했지만, 동시에 현실 세계의 모든 복잡성을 담아내기에는 여러 한계가 존재한다는 점도 명확히 인지하게 되었습니다.
가장 큰 한계점은 정적인 데이터의 사용입니다. 현재 시스템은 역간 이동 시간과 환승 시간을 고정된 값으로 사용합니다. 하지만 실제 지하철 환경은 매우 동적입니다. 예를 들어, 출퇴근 시간대에는 엄청난 인파로 인해 환승 통로를통과하는 시간이 평소보다 훨씬 길어질 수 있으며, 주말이나 공휴일의 배차 간격 변화 또한 현재 모델에는 반영되어 있지 않습니다.
두 번째로, 역 내부의 물리적 특성을 고려하지 못했다는 점입니다. 모든 환승역의 구조는 저마다 다릅니다. 종로3가처럼 환승 통로가 매우 길고 복잡한 역이 있는가 하면, 어떤 역은 엘리베이터나 에스컬레이터 없이 계단만으로 이루어져 있어 교통 약자의 이동 시간이 더 길어질 수 있습니다. 저희 모델은 이러한 개별 역의 특성을 반영하지 못하고, 모든 환승 시간을 평균적인 값으로 처리했습니다. 이는 실제 사용자가 체감하는 소요 시간과 오차를 발생시킬 수 있는 부분입니다.
이러한 한계들은 곧 다음 단계의 도전 과제가 될 것입니다. 만약 실시간 열차 도착 정보나 시간대별 혼잡도 데이터를 시스템에 연동하고, 각 역의 물리적 구조에 따른 상세한 환승 소요 시간 데이터를 구축할 수 있다면, 지금보다 훨씬 더 정교하고 사용자에게 실질적인 도움이 되는 최적 경로 탐색 시스템으로 발전할 수 있을 것이라 생각합니다.
텍스트로만 존재하던 경로가 folium 지도 위에서 다채로운 색상의 노선으로 그려지는 것을 끝으로 프로젝트가 마무리되었다고 느꼈습니다. 이번 프로젝트는 저에게 '성장' 그 자체였습니다. 머릿속에 흩어져 있던 이론의 조각들이 손끝에서 하나의 의미 있는 서비스로 완성되는 짜릿한 경험이었습니다. 데이터를 다루는 현실적인 어려움부터, 알고리즘의 깊이 있는 이해, 그리고 예상치 못한 문제에 대한 창의적인 해결까지. 이번 경험은 앞으로 저의 여정에 든든한 밑거름이 되어줄 것입니다.