지하철 노선 최단경로, 최소환승 찾기 ( Find the Shortest Path and Minimum Transfer for Seoul Metro )

Sample

Source Code

main.cpp

cpp
#define MAX_STATION 398
// ㄴ 지하철 역 갯수
#include "Graph.h"

int main()
{
 Graph test; // 그래프 선언

 test.Subway("subway.txt",MAX_STATION); // 지하철 경로 찾기 프로그램 시작!

 return 0; // 끝
}

Graph.h

cpp
#ifndef GRAPH_H
#define GRAPH_H

#include <stack> // 완성된 클라우드에서 리커시브함수로 경로를 저장할때 사용
#include <string> // 역이름 클래스


class Edge // 엣지 클래스..
{
public:
 int id; // 역 번호
 int time; // 이동시간
 int transfer; // 환승 횟수
 Edge* next;
 Edge() : next(NULL) {}
};

class Graph // 그래프 클래스..
{
private:
 ofstream outputfile;
 string* station; // 역 번호에 따른 역 이름
 Edge* graph; // 그래프 (adjacency list)
 int* route; // 음수면 클라우드에 포함되지 않은 버텍스, 음수가 아니면 클라우드에 포함된 버텍스
 int n; // 지하철 역 갯수
public:
 int Choose(bool t); // 클라우드에 포함되지 않은 버텍스 중, cost가 최소인 버텍스의 인덱스를 반환. t에따라 요소가 달라짐
 void DijkstraAlgorithm(int start,bool t); // Dijkstra Algorithm 구현부분
 void Subway(const char* name, int N); // 출발역,도착역을 입력 받고 Dijkstra Algorithm을 실행하여 최단시간,최소환승 경로를 출력해줌
 bool FindRoute(stack<int>& s, int start, int end); // Dijkstra Algorithm을 실행한 후의 그래프에서 경로를 스택에 옮겨주는 재귀함수
};

#endif

Graph.cpp

cpp
#include "Graph.h"

int Graph::Choose(bool t) // 최소인 버텍스의 인덱스를 반환
{
 int min=99999,min_transfer=9999,pos=-1; 

 if(t) // 최단시간 경로일떄 
 {

  for(int i=0;i<n;i++)
  {
   if(route[i] < 0)
   {
    if(graph[i].time < min) // 시간이 덜드는 버텍스를 선택
    {
     min = graph[i].time;
     min_transfer = graph[i].transfer;
     pos = i;
    }
    else if(graph[i].time == min)
    {
     if(graph[i].transfer < min_transfer)
     {
      min = graph[i].time;
      min_transfer = graph[i].transfer;
      pos = i;
     }
    }
   }
  }

 }
 else // 최소환승 경로일때
 {

  for(int i=0;i<n;i++)
  {
   if(route[i] < 0)
   {
    if(graph[i].transfer < min_transfer) // 환승 횟수가 작은 버텍스를 선택
    {
     min = graph[i].time;
     min_transfer = graph[i].transfer;
     pos = i;
    }
    else if(graph[i].transfer == min_transfer) // 환승 횟수가 같으면
    {
     if(graph[i].time < min) // 시간이 덜드는 버텍스를 선택
     {
      min = graph[i].time;
      min_transfer = graph[i].transfer;
      pos = i;
     }
    }
   }
  }

 }
 return pos; // 인덱스 반환
}

void Graph::DijkstraAlgorithm(int start, bool t) // Dijskstra Algorithm 
{
 int minpos; 


 // 그래프와 route배열 초기화
 for(int i=0;i<n;i++)
 {
  route[i] = -1;
  graph[i].id = -1;
  graph[i].time = 99999;
  graph[i].transfer = 9999;
 }

 // 시작점과 연결된 버텍스에 엣지의 코스트를 대입
 for(Edge* p=graph[start].next;p!=NULL;p=p->next)
 {
  
  if(station[start] == station[p->id]) // 시작점과 연결된 버텍스가 환승역일때
   // 출발역이 환승역인 경우는 환승 횟수와 시간을 0으로 따져야 한다.
  {
   graph[p->id].time = 0;
   graph[p->id].transfer = 0;
  }
  else // 일반적인 경우
  {
   graph[p->id].time = p->time;
   graph[p->id].transfer = p->transfer;
  }
 }


 // 출발역이 환승역인 경우. 출발역과 같은 이름을 가진 역 번호를 가진 엣지들의 값을 모두 0으로 만들어줘야한다
 // bug fix.. (환승역 -> 환승역 경로찾기시 경로 찾기 실패)
 for(int i=0;i<n;i++)
 {
  if(station[start] == station[i])
  {
   for(Edge* p=graph[i].next;p!=NULL;p=p->next)
   {
    if(station[i] == station[p->id])
    {
     p->time = 0;
     p->transfer = 0;
    }
   }
  }
 }


 // 시작점을 클라우드에 포함시킨다
 //route[start] = start;
 route[start] = 0;
 // 시작점 초기화
 graph[start].time = 0;
 graph[start].transfer = 0;


 for(int i=0,prev=start;i<n-2;i++)
 {
  // 최소인 버텍스 선택
  minpos = this->Choose(t);

  //route[minpos] = prev;

  // 최소인 버텍스 클라우드에 포함시킨다
  route[minpos] = 0;
  
  // 선택된 버텍스에 연결된 엣지들로 다른 버텍스의 값을 업데이트시킨다 
  for(Edge* p=graph[minpos].next;p!=NULL;p=p->next)
  {
   if(t) // 최단시간 경로일때
   {
    if(graph[minpos].time + p->time < graph[p->id].time) // 시간을 비교하여 업데이트
    {
     graph[p->id].time = graph[minpos].time + p->time;
     graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
    }
    else if(graph[minpos].time + p->time == graph[p->id].time) // 시간이 같을때.. 환승횟수가 적은게 좋겠죠?(상식..ㅠ)
    {
     if(graph[minpos].transfer + p->transfer < graph[p->id].transfer) // 환승횟수를 비교
     {
      graph[p->id].time = graph[minpos].time + p->time;
      graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
     }
    }
   }
   else // 최소환승 경로일때
   {
    if(graph[minpos].transfer + p->transfer < graph[p->id].transfer) // 환승횟수를 비교하여 업데이트
    {
     graph[p->id].time = graph[minpos].time + p->time;
     graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
    }
    else if(graph[minpos].transfer + p->transfer == graph[p->id].transfer) // 환승횟수가 같으면
    {
     if(graph[minpos].time + p->time < graph[p->id].time) // 시간을 비교
     {
      graph[p->id].time = graph[minpos].time + p->time;
      graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
     }
    }
   }
   
  }

  //prev = minpos;

 }

}

void Graph::Subway(const char* name, int N) 
{
 
 fstream file;
 int start=-1,end=-1;
 int min,v,prev;
 string t; // 임시 스트링 변수
 stack<int> s,r; // 스택 s,r
 Edge* temp; // 임시 엣지포인터 변수
 Edge* p; // 임시 엣지포인터 변수
 n = N; // 지하철 역 갯수 초기화

 // 클래스 데이터 초기화
 graph = new Edge[n];
 station = new string[n];
 route = new int[n];

 file.open(name,ios::in); // 파일 읽기 (ios::in -> 읽기)

 int t1,t2,time;
 string s1,s2;
 while(!file.eof())
 {
  // 임시 변수에 한 줄의 데이터 입력
  file >> t1;
  file >> t2;
  file >> time;
  file >> s1;

  // 버그방지용
  // 파일 마지막 공백문자 같은 엉뚱한 문자가 있을때 멈춘다
  if(file.eof())
   break;

  file >> s2;

  //끝

  // 인덱스에 넣기위해 역 번호에서 1씩 빼준다
  t1-=1;
  t2-=1;

  // 엣지를 만든다 (1)
  temp = new Edge();
  temp->id = t2;
  temp->time = time;
  if(s1==s2) temp->transfer = 1;
  else temp->transfer = 0;
 
  // 서로의 버텍스에 엣지를 연결한다 (1)
  p=&graph[t1];
  while(p->next!=NULL)
  {
   p=p->next;
  }
  p->next = temp;

  // 엣지를 만든다 (2)
  temp = new Edge();
  temp->id = t1;
  temp->time = time;
  if(s1==s2) temp->transfer = 1;
  else temp->transfer = 0;
 
  // 서로의 버텍스에 엣지를 연결한다 (2)
  p=&graph[t2];
  while(p->next!=NULL)
  {
   p=p->next;
  }
  p->next = temp;


  // 역 이름 배열에 역 이름을 저장한다
  station[t1] = s1;
  station[t2] = s2;


 }
  
 file.close();
 //끝-파일입력


 // 출발역,도착역 입력!!!!!!
 while(start==end)
 {

  while(start < 0)
  {
   std::cout << "출발역을 입력하세요...\n : ";
   cin >> t;
   std::cout << std::endl;  

   // 출발역 이름과 같은 역번호 아무거나 하나 찾는다
   for(int i=0;i<n;i++)
   {
    if(station[i] == t)
    {
     start = i;
     break;
    }
   }
 
   //없으면
   if(start < 0)
   {
    std::cout << "잘못 입력하셨습니다." << std::endl;
    
   }
  }

  while(end < 0)
  {

   std::cout <<  "도착역을 입력하세요...\n : ";
   cin >> t;
   std::cout << std::endl;

  
   // 도착역 이름과 같은 역번호 아무거나 하나 찾는다
   for(int i=0;i<n;i++)
   {
    if(station[i] == t)
    {
     end = i;
     break;
    }
   }
  
   //없으면
   if(end < 0)
   {
    std::cout << "잘못 입력하셨습니다." << std::endl;
    
   }

  }

  if(start==end)
  {
   std::cout << "출발역과 도착역이 같습니다...." << std::endl;
   start = end = -1;
  }
 }



 std::cout << "찾고자 하는 구간 : " << station[start] << " -> " << station[end] << std::endl << std::endl;
 std::cout << "* 최단시간 경로 :" << std::endl;
 this->DijkstraAlgorithm(start,true); // 알고리즘 실행 (true이므로 최단시간 경로)

 // 도착역 중, 가장 소요시간이 작은 버텍스를 선택한다
 min=graph[end].time;
 for(int i=0;i<n;i++)
 {
  if(station[end] == station[i])
  {
   if(graph[i].time < min)
   {
    min = graph[i].time;
    end = i;
   }
  }
 }

 // 출발역의 인덱스와 찾은 버텍스의 인덱스로 경로를 스택에 저장한다. 
 this->FindRoute(s,start,end);

 // 스택에서 스택으로 옮긴다 (순서 역순으로 바꾸기)
 while(!s.empty())
 {
  r.push(s.top());
  s.pop();
 }

 // 경로 출력
 for(v=0,prev=-1;!r.empty();v++)
 {
  if(prev != -1 && station[prev] == station[r.top()])
  {
   if(station[r.top()] != station[start])
    std::cout << "(환승)";

   v--;
   prev = r.top();
   r.pop();
  }
  else
  {
  if(v!=0)
   std::cout << " -> ";
  else
   std::cout << " ";

  std::cout << station[r.top()];
  prev = r.top();
  r.pop();

  }
 }
 std::cout << std::endl <<  "\t-->" << v-1 << "개역 지남" << std::endl
  << "\t-->" << graph[end].time/60 << "시간 " << graph[end].time%60 << "분 걸리고, " << graph[end].transfer << "번 환승합니다." << std::endl;

 std::cout << std::endl;
 std::cout << "* 최소환승 경로 :" << std::endl;
 this->DijkstraAlgorithm(start,false); // 알고리즘 실행 (false- 최소환승경로)

 // 도착역 버텍스 중에 환승횟수가 가장 작은 버텍스를 선택
 min=graph[end].transfer;
 for(int i=0;i<n;i++)
 {
  if(station[end] == station[i])
  {
   if(graph[i].transfer < min)
   {
    min = graph[i].transfer;
    end = i;
   }
  }
 }

 // 경로찾기
 this->FindRoute(s,start,end);

 // 스택에서 스택으로 옮김
 while(!s.empty())
 {
  r.push(s.top());
  s.pop();
 }

 //출력
 for(v=0,prev=-1;!r.empty();v++)
 {
  if(prev != -1 && station[prev] == station[r.top()])
  {
   if(station[r.top()] != station[start])
    std::cout << "(환승)";

   v--;
   prev = r.top();
   r.pop();
  }
  else
  {
  if(v!=0)
   std::cout << " -> ";
  else
   std::cout << " ";
  
  std::cout << station[r.top()];
  prev = r.top();
  r.pop();
  }
 }
 std::cout << std::endl <<  "\t-->" << v-1 << "개역 지남" << std::endl
  << "\t-->" << graph[end].time/60 << "시간 " << graph[end].time%60 << "분 걸리고, " << graph[end].transfer << "번 환승합니다." << std::endl;


}

bool Graph::FindRoute(stack<int> &s, int start, int end) // 완성된 클라우드 에서 경로찾기
{
 s.push(start); // 스택에 넣는다.

 if(start == end) // 시작=끝 일때 경로찾았다고 알려줌 (return true)
  return true;

 for(Edge* p=graph[start].next;p!=NULL;p=p->next) // 시작점에 연결된 엣지를 모두 조사한다
 { 
  // 시작점버텍스값 + 엣지값 과 엣지로연결된 버텍스의 값이 같으면 (DijkstraAlgorithm에서 클라우드에 포함시킬떄 연결한 경로)
  if(graph[start].time + p->time == graph[p->id].time && graph[start].transfer + p->transfer == graph[p->id].transfer)
  {
   if(!this->FindRoute(s,p->id,end)) // 다음 경로로 이동 했는데 경로가 없다면
   {
    s.pop(); // pop한다
   }
   else // 경로를 찾았으면 pop하지않고 유지
   {
    return true; // 경로를 찾았다고 알려줌
   }
  }
 }
 return false;
}

Input

subway.txt

txt
1 2 3 소요산 동두천
2 3 3 동두천 보산
3 4 3 보산 동두천중앙
4 5 3 동두천중앙 지행
5 6 3 지행 덕정
6 7 3 덕정 덕계
7 8 3 덕계 주내
8 9 3 주내 녹양
9 10 3 녹양 가능
10 11 3 가능 의정부
11 12 2 의정부 회룡
12 13 3 회룡 망월사
13 14 2 망월사 도봉산
14 15 3 도봉산 도봉
15 16 2 도봉 방학
16 17 2 방학 창동
17 18 3 창동 녹천
18 19 2 녹천 월계
19 20 2 월계 성북
20 21 2 성북 석계
21 22 2 석계 신이문
22 23 2 신이문 외대앞
23 24 3 외대앞 회기
24 25 2 회기 청량리
25 26 2 청량리 제기동
26 27 1 제기동 신설동
27 28 1 신설동 동묘앞
28 29 1 동묘앞 동대문
29 30 1 동대문 종로5가
30 31 2 종로5가 종로3가
31 32 2 종로3가 종각
32 33 3 종각 시청
33 34 2 시청 서울역
34 35 3 서울역 남영
35 36 2 남영 용산
36 37 3 용산 노량진
37 38 3 노량진 대방
38 39 2 대방 신길
39 40 2 신길 영등포
40 41 2 영등포 신도림
41 42 2 신도림 구로
42 43 3 구로 구일
43 44 2 구일 개봉
44 45 2 개봉 오류동
45 46 3 오류동 온수
46 47 1 온수 역곡
47 48 2 역곡 소사
48 49 2 소사 부천
49 50 2 부천 중동
50 51 2 중동 송내
51 52 1 송내 부개
52 53 2 부개 부평
53 54 2 부평 백운
54 55 3 백운 동암
55 56 2 동암 간석
56 57 2 간석 주안
57 58 2 주안 도화
58 59 3 도화 제물포
59 60 3 제물포 도원
60 61 3 도원 동인천
61 62 2 동인천 인천
42 63 5 구로 가산
63 64 3 가산 독산
64 65 3 독산 시흥
65 66 3 시흥 석수
66 67 3 석수 관악
67 68 3 관악 안양
68 69 3 안양 명학
69 70 4 명학 금정
70 71 4 금정 군포
71 72 4 군포 의왕
72 73 4 의왕 성균관대
73 74 4 성균관대 화서
74 75 4 화서 수원
75 76 4 수원 세류
76 77 4 세류 병점
77 78 4 병점 세마
78 79 4 세마 오산대
79 80 4 오산대 오산
80 81 4 오산 진위
81 82 4 진위 송탄
82 83 4 송탄 서정리
83 84 4 서정리 지제
84 85 4 지제 평택
85 86 4 평택 선환
86 87 4 선환 직산
87 88 4 직산 두정
88 89 4 두정 천안
65 90 5 시흥 광명
91 92 2 낙성대 사당
92 93 3 사당 방배
93 94 2 방배 서초
94 95 2 서초 교대
95 96 2 교대 강남
96 97 1 강남 역삼
97 98 2 역삼 선릉
98 99 2 선릉 삼성
99 100 2 삼성 종합운동장
100 101 2 종합운동장 신천
101 102 2 신천 잠실
102 103 2 잠실 성내
103 104 3 성내 강변
104 105 1 강변 구의
105 106 3 구의 건대입구
106 107 2 건대입구 성수
107 108 2 성수 뚝섬
108 109 3 뚝섬 한양대
109 110 2 한양대 왕십리
110 111 1 왕십리 상왕십리
111 112 2 상왕십리 신당
112 113 2 신당 동대문운동장
113 114 2 동대문운동장 을지로4가
114 115 2 을지로4가 을지로3가
115 116 2 을지로3가 을지로입구
116 117 1 을지로입구 시청
117 118 1 시청 충정로
118 119 3 충정로 아현
119 120 2 아현 이대
120 121 1 이대 신촌
121 122 2 신촌 홍대입구
122 123 2 홍대입구 합정
123 124 2 합정 당산
124 125 2 당산 영등포구청
125 126 2 영등포구청 문래
126 127 2 문래 신도림
127 128 3 신도림 대림
128 129 2 대림 구로디
129 130 2 구로디 신대방
130 131 2 신대방 신림
131 132 2 신림 봉천
132 133 2 봉천 서울대입구
133 91 2 서울대입구 낙성대
134 135 3 수서 일원
135 136 2 일원 대청
136 137 2 대청 학여울
137 138 1 학여울 대치
138 139 2 대치 도곡
139 140 2 도곡 매봉
140 141 2 매봉 양재
141 142 3 양재 남부터미널
142 143 2 남부터미널 교대
143 144 2 교대 고속터미널
144 145 2 고속터미널 잠원
145 146 2 잠원 신사
146 147 3 신사 압구정
147 148 2 압구정 옥수
148 149 2 옥수 금호
149 150 1 금호 약수
150 151 2 약수 동대입구
151 152 2 동대입구 충무로
152 153 1 충무로 을지로3가
153 154 1 을지로3가 종로3가
154 155 2 종로3가 안국
155 156 2 안국 경복궁
156 157 3 경복궁 독립문
157 158 2 독립문 무악재
158 159 2 무악재 홍제
159 160 2 홍제 녹번
160 161 2 녹번 불광
161 162 2 불광 연신내
162 163 3 연신내 구파발
163 164 3 구파발 지축
164 165 4 지축 삼송
165 166 4 삼송 원당
166 167 3 원당 화정
167 168 4 화정 대곡
168 169 3 대곡 백석
169 170 3 백석 마두
170 171 2 마두 정발산
171 172 3 정발산 주엽
172 173 2 주엽 대화
174 175 4 오이도 정왕
175 176 4 정왕 신길온천
176 177 4 신길온천 안산
177 178 2 안산 공단
178 179 3 공단 고잔
179 180 2 고잔 중앙
180 181 3 중앙 한대앞
181 182 3 한대앞 상록수
182 183 3 상록수 반월
183 184 4 반월 대야미
184 185 3 대야미 수리산
185 186 2 수리산 산본
186 187 3 산본 금정
187 188 3 금정 범계
188 189 2 범계 평촌
189 190 4 평촌 인덕원
190 191 3 인덕원 정부종합청사
191 192 2 정부종합청사 과천
192 193 2 과천 대공원
193 194 2 대공원 경마공원
194 195 3 경마공원 선바위
195 196 3 선바위 남태령
196 197 1 남태령 사당
197 198 2 사당 이수
198 199 3 이수 동작
199 200 4 동작 이촌
200 201 2 이촌 신용산
201 202 1 신용산 삼각지
202 203 2 삼각지 숙대입구
203 204 2 숙대입구 서울역
204 205 2 서울역 회현
205 206 2 회현 명동
206 207 1 명동 충무로
207 208 2 충무로 동대문운동장
208 209 2 동대문운동장 동대문
209 210 2 동대문 혜화
210 211 2 혜화 한성대입구
211 212 3 한성대입구 성신여대입구
212 213 2 성신여대입구 길음
213 214 2 길음 미아삼거리
214 215 2 미아삼거리 미아
215 216 3 미아 수유
216 217 2 수유 쌍문
217 218 2 쌍문 창동
218 219 2 창동 노원
219 220 2 노원 중계
220 221 3 중계 상계
221 222 3 상계 당고개
223 224 2 용산 이촌
224 225 2 이촌 서빙고
225 226 2 서빙고 한남
226 227 2 한남 옥수
227 228 2 옥수 응봉
228 229 2 응봉 왕십리
229 230 2 왕십리 청량리상
230 231 2 청량리상 회기
231 232 2 회기 중랑
232 233 3 중랑 상봉
233 234 3 상봉 망우
234 235 3 망우 양원
235 236 4 양원 구리
236 237 4 구리 도농
237 238 4 도농 양정
238 239 4 양정 덕소
240 241 2 방화 개화산
241 242 2 개화산 김포공항
242 243 2 김포공항 송정
243 244 2 송정 마곡
244 245 2 마곡 발산
245 246 2 발산 우장산
246 247 2 우장산 화곡
247 248 2 화곡 까치산
248 249 2 까치산 신정
249 250 2 신정 목동
250 251 2 목동 오목교
251 252 2 오목교 양평
252 253 2 양평 영등포구청
253 254 2 영등포구청 문래
254 255 2 문래 영등포시장
255 256 2 영등포시장 신길
256 257 2 신길 여의도
257 258 2 여의도 여의나루
258 259 2 여의나루 마포
259 260 2 마포 공덕
260 261 2 공덕 애오개
261 262 2 애오개 충정로
262 263 2 충정로 서대문
263 264 2 서대문 광화문
264 265 2 광화문 종로3가
265 266 2 종로3가 을지로4가
266 267 2 을지로4가 동대문운동장
267 268 2 동대문운동장 청구
268 269 2 청구 신금호
269 270 2 신금호 행당
270 271 2 행당 왕십리
271 272 2 왕십리 마장
272 273 2 마장 답십리
273 274 2 답십리 장한평
274 275 2 장한평 군자
275 276 2 군자 아차산
276 277 2 아차산 광나루
277 278 2 광나루 천호
278 279 2 천호 강동
279 280 2 강동 둔촌동
280 281 2 둔촌동 올림픽공원
281 282 2 올림픽공원 방이
282 283 2 방이 오금
283 284 2 오금 개롱
284 285 2 개롱 거여
285 286 3 거여 마천
279 287 2 강동 길동
287 288 2 길동 굽은다리
288 289 2 굽은다리 명일
289 290 2 명일 고덕
290 291 3 고덕 상일동
292 293 2 봉화산 화랑대
293 294 2 화랑대 태릉입구
294 295 2 태릉입구 석계
295 296 2 석계 돌곶이
296 297 2 돌곶이 상월곡
297 298 2 상월곡 월곡
298 299 2 월곡 고려대
299 300 2 고려대 안암
300 301 2 안암 보문
301 302 2 보문 창신
302 303 2 창신 동묘앞
303 304 2 동묘앞 신당
304 305 2 신당 청구
305 306 2 청구 약수
306 307 2 약수 버티고개
307 308 2 버티고개 한강진
308 309 2 한강진 이태원
309 310 2 이태원 녹사평
310 311 2 녹사평 삼각지
311 312 2 삼각지 효창공원앞
312 313 2 효창공원앞 공덕
313 314 2 공덕 대흥
314 315 2 대흥 광흥창
315 316 2 광흥창 상수
316 317 2 상수 합정
317 318 2 합정 망원
318 319 2 망원 마포구청
319 320 2 마포구청 성산
320 321 2 성산 수색
321 322 2 수색 증산
322 323 2 증산 새절
323 324 2 새절 응암
324 325 2 응암 역촌
325 326 2 역촌 불광
326 327 2 불광 독바위
327 328 2 독바위 연신내
328 329 2 연신내 구산
329 324 2 구산 응암
330 331 2 장암 도봉산
331 332 2 도봉산 수락산
332 333 2 수락산 마들
333 334 2 마들 노원
334 335 2 노원 중계
335 336 2 중계 하계
336 337 2 하계 공릉
337 338 2 공릉 태릉입구
338 339 2 태릉입구 먹골
339 340 2 먹골 중화
340 341 2 중화 상봉
341 342 2 상봉 면목
342 343 2 면목 사가정
343 344 2 사가정 용마산
344 345 2 용마산 중곡
345 346 2 중곡 군자
346 347 2 군자 어린이대공원
347 348 2 어린이대공원 건대입구
348 349 2 건대입구 뚝섬유원지
349 350 2 뚝섬유원지 청담
350 351 2 청담 강남구청
351 352 2 강남구청 학동
352 353 2 학동 논현
353 354 2 논현 반포
354 355 2 반포 고속터미널
355 356 2 고속터미널 내방
356 357 2 내방 이수
357 358 2 이수 남성
358 359 2 남성 숭실대입구
359 360 2 숭실대입구 상도
360 361 2 상도 장승배기
361 362 2 장승배기 신대방삼거리
362 363 2 신대방삼거리 보라매
363 364 2 보라매 신풍
364 365 2 신풍 대림
365 366 2 대림 남구로
366 367 2 남구로 가산
367 368 2 가산 철산
368 369 2 철산 광명사거리
369 370 2 광명사거리 천왕
370 371 2 천왕 온수
372 373 2 암사 천호
373 374 2 천호 강동구청
374 375 2 강동구청 몽촌토성
375 376 2 몽촌토성 잠실
376 377 2 잠실 석촌
377 378 2 석촌 송파
378 379 2 송파 가락시장
379 380 2 가락시장 문정
380 381 2 문정 장지
381 382 2 장지 복정
382 383 2 복정 산성
383 384 2 산성 남한산성입구
384 385 2 남한산성입구 단대오거리
385 386 2 단대오거리 신흥
386 387 2 신흥 수진
387 388 2 수진 모란
389 390 3 신설동 용두
390 391 3 용두 신답
391 392 3 신답 용답
392 393 3 용답 성수
394 395 2 까치산 신정네거리
395 396 2 신정네거리 양천구청
396 397 2 양천구청 도림천
397 398 2 도림천 신도림
398 41 5 신도림 신도림
41 127 5 신도림 신도림
398 127 3 신도림 신도림
393 107 3 성수 성수
389 27 5 신설동 신설동
394 248 5 까치산 까치산
63 367 5 가산 가산
106 348 5 건대입구 건대입구
144 355 5 고속터미널 고속터미널
313 260 5 공덕 공덕
95 143 5 교대 교대
275 346 5 군자 군자
70 187 5 금정 금정
287 287 5 길동 길동
219 334 5 노원 노원
128 365 5 대림 대림
14 331 5 도봉산 도봉산
29 209 5 동대문 동대문
113 208 5 동대문운동장 동대문운동장
208 267 5 동대문운동장 동대문운동장
113 267 5 동대문운동장 동대문운동장
28 303 5 동묘앞 동묘앞
126 254 5 문래 문래
161 326 5 불광 불광
92 197 5 사당 사당
202 311 5 삼각지 삼각지
34 204 5 서울역 서울역
21 295 5 석계 석계
33 117 5 시청 시청
39 256 5 신길 신길
112 304 5 신당 신당
150 306 5 약수 약수
162 328 5 연신내 연신내
125 253 5 영등포구청 영등포구청
148 227 5 옥수 옥수
46 371 5 온수 온수
110 229 5 왕십리 왕십리
229 271 5 왕십리 왕십리
271 110 5 왕십리 왕십리
36 223 5 용산 용산
115 153 5 을지로3가 을지로3가
114 266 5 을지로4가 을지로4가
198 357 5 이수 이수
200 224 5 이촌 이촌
102 376 5 잠실 잠실
31 154 5 종로3가 종로3가
154 265 5 종로3가 종로3가
265 31 5 종로3가 종로3가
17 218 5 창동 창동
278 373 5 천호 천호
268 305 5 청구 청구
152 207 5 충무로 충무로
118 262 5 충정로 충정로
294 338 5 태릉입구 태릉입구
123 317 5 합정 합정
24 231 5 회기 회기