Dijkstra Algorithm을 이용한 지하철 최단경로 구하기

Specification

문제 : 지하철에서 최단 경로 구하기

지하철에서 두 지점 간의 최단 시간 경로를 구하는 데 다음을 가정한다.

1. 지하철은 n(n <= 10)개의 노선이 있다, I 번째 노선의 역 이름은 제일 왼쪽 역부터 I-1, I-2, I-3 .......으로 주어진다. 각 노선별 역의 수는 50보다 작거나 같다.

2. 환승역에서는 두 개의 노선사이에서만 환승할 수 있다. 그러므로 환승역은 두 개의 역이름이 주어진다 (예 : 1-5, 2-3)

3. 출발역과 도착역은 환승역이 아니라고 가정한다.

4. 역과 역사이의 운행시간은 모두 1로 한다. 환승 시간 t는 입력으로 주어진다.

입력

입력 파일의 이름은 input.txt이다.

3 // 지하철 노선의 수

1 14 // 1 번 노선의 역의 수

2 14 // 2 번 노선의 역의 수

3 16 // 3 번 노선의 역의 수

6 // 환승역의 수

1 5 2 3 // 1번 노선 5번역과 2번 노선 3번역

1 6 3 2

1 10 2 9

1 12 3 13

2 5 3 5

2 13 3 15

2 // 테스트할 데이터의 수

0 2 2 3 14 // 환승시간 0 , 2번 노선 2번역에서 출발 3번 노선 14번역에 도착

5 1 3 2 4 // 환승시간 5 , 1번 노선 3번역에서 출발 2번 노선 4번역에 도착

출력

출력은 다음과 같은 형식으로 한다.

9 // 첫 번째 데이터의 최단 경로 시간

8 // 두 번째 데이터의 최단 경로 시간 

Problem Solve

1. 개요

 

▮ 지하철은 n(n <= 10)개의 노선이 있다.

▮ ⅰ번째 노선의 역 이름은 제일 왼쪽 역부터 ⅰ-1, ⅰ-2, ⅰ-3... 으로 주어진다.

▮ 각 노선별 역의 수는 50보다 작거나 같다.

▮ 환승역에서만 두 개의 노선사이에서 환승하 수 있다.

▮ 출발역과 도착역은 환승역이 아니라고 가정한다.

▮ 역과 역사이의 운행시간은 모두 1이며, 환승시간은 입력으로 주어진다.

 

2. 알고리즘 구성 및 설명

 

1) void init()

 

▮ 파일 입력을 통해 각 데이터들을 입력받습니다.

▮ 우선 전체 호선 수를 변수에 따로 저장하고 배열변수에 이용해 각 호선의 역 수를 저장합니다. 그리고 각 호선의 역수를 전부 더하여 총 역의 개수를 구합니다. 

▮ 이후 총 역의 개수를 이용하여 2중배열로 지하철역을 표현합니다. 

▮ 마찬가지로 환승역 역시 변수 하나에 환승역 총 수를 저장하고 배열을 이용하여 각 환승역의 출발역과 도착역을 저장합니다.

▮ 출발역 도착역은 호선에 상관없이 전체 지하철역에서 몇 번째 역인지로 표현됩니다. 즉, 주어진 예시에서처럼 14 14 16 으로 지하철역이 주어져 있다면 2-3역은 17로 저장됩니다. 이를 역의 고유번호로 정의합니다. 

▮ 마지막으로 경로를 찾는 횟수를 변수로 저장하고 환승시간, 출발역, 도착역을 배열에 저장합니다.

 

2) void make_map(int trans_time)

 

▮ init()에서 입력받은 데이터들을 바탕으로 실질적으로 지하철 노선을 구성하는 단계입니다.

▮ 각 경로 탐색 회차에 따라 다른 환승시간에 따라 재구성 됩니다. 즉, 지하철 역을 표현하는 이중배열 자체는 초기화 단계에서 생성되지만 내용은 회차마다 다르게 구성됩니다.

▮ 우선 이중배열 전체를 무한대(여기선 9999를 무한대로 간주합니다.)로 채웁니다.

▮ 이중배열은 subway_map[i][j]로 표현되었고 이는 i역에서 j역으로 가는 시간을 나타냅니다.

▮ 따라서 subway_map[i][i] = 0이고 subway_map[i][i-1] = 1 subway_map[i][i+1] = 1로 표현할 수 있습니다.

▮ 일반적인 역은 바로 전과 바로 뒤 역으로 이동할 수 있지만 환승역의 경우 앞서 정의했던 역의 고유번호대로 표현된 이중배열 이므로 특정역에서 다른 호선의 다른역으로 이동할 수 있다고 표현하였습니다.

 

3) int path_finder(int phase)

 

▮ 몇번째 경로탐색인지를 입력받아 최소경로 시간을 리턴해주는 함수 입니다.

▮ 최소경로 탐색의 회차를 index로 하는 배열에 출발역과 도착역이 저장되어 있기 때문에 경로탐색의 회차를 입력받습니다.

▮ 출발역을 기준으로 Dijkstra Algorithm을 통해 출발역으로 부터 모든 역까지의 시간을 저장합니다. 이때 length[]는 기준역에서 부터 해당 index에 해당하는 역까지의 길이를 저장했다가 탐색이 끝난 역에는 –1이 되므로 length_mirror[]라는 자료구조를 이용하여 각 역까지의 길이를 동시에 저장해둡니다.

▮ 도착역을 index로 하여 length_mirror[]의 값을 최종 시간으로 저장하여 리턴합니다.

 

3) int main()

 

▮ 총 지하철 호선수를 검사하여 10개를 초과할 경우 에러메시지를 띄우고 프로그램을 종료시킵니다.

▮ 각 호선을 검사하여 역의 수가 50개를 초과하는 경우 에러메시지를 띄우고 프로그램을 종료시킵니다.

▮ 각 회차만큼 반복하여 지하철 노선을 재구성하고 최소경로의 이동시간을 출력합니다. 

 

3. 지하철 환승역을 표현하기 위한 자료구조

 

▮ 이 프로그램에서는 환승역을 표현하기 위해 두가지 장치를 활용하였습니다.

▮ 첫 번째 장치는 모든 역에 고유번호를 부과하여 이 고유 번호를 환승역의 출발역과 도착역에 저장을 하였습니다.

▮ 두 번째 장치로 이를 이중배열을 이용한 지하철 노선에 표현하였습니다. 

▮ 예를 들어 첫번째 환승역이 1-5 2-3이라고 한다면 fr_trans_station[0] = 5, to_trans_station[0] = 17이 됩니다.

▮ 이를 이중배열에 subway_map[5][17] = transfer time, subway_map[17][5] = transfer time로 표현하여 1-5 역에서 1-4, 1-6으로 갈 수도 있지만 2-3으로도 갈 수 있음을 표현하였습니다.

▮ 이중배열이 아닌 그래프로 본다면 1-5 2-3은 하나의 역이지만 두개의 노드를 가지며 1-5와 2-3은 서로 다른 2개의 directed edge로 서로를 가리키고 있으며 이 때의 weight가 transfer time이 됩니다.

4. 소스코드