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. 소스코드

	/****************************************************************************
	최종 수정일: 2011-05-25
	Dijkstra's Algorithm을 이용하여 지하철의 최소경로를 구하는 Algorithm 설계 입니다.
	Windows Visual Studio 2010 환경에서 설계되었습니다.
	각각의 지하철 역은 1-1 부터 마지막 호선 마지막 역까지 일정한 번호가 부여되었으며
	그 번호가 역의 이름을 대신하도록 했습니다.
	*****************************************************************************/
	#include <stdio.h>
	#include <iostream>
	#include <fstream>
	#define MAX_LINES 10 // 지하철 최대 호선수
	#define MAX_STATION 50 // 호선당 최대 역의 수
	#define INFINITE 9999 // link되어 있지 않음을 표현하기 위해 무한대를 정수로 정의하였음
	using namespace std;
	ifstream fin("input.txt");
	// 지하철 구성용 변수 및 자료구조
	int tot_lines; // 지하철 호선의 수
	int tot_stations; // 총 지하철 역의 수
	int *num_of_line; //각 호선당 역의 수 (1부터 index 즉, 1호선은 num_of_line[1])
	int **subway_map; // 지하철 역 그래프를 2차원 배열로 나타냄
	// 지하철 환승정보 변수 및 자료구조
	int tot_trans; // 환승역 갯수
	int line_index; // 환승역 호선
	int station_index; // 환승역 역
	int *fr_trans_station; // 출발 환승역, 반대가 될 수도 있음
	int *to_trans_station; // 도착 환승역, 반대가 될 수도 있음
	// 경로 탐색용 변수 및
	int phase; // 몇개의 최단경로를 구할 것인가
	int *transfer_time; // 각 회차에서의 환승 소요시간
	int *start_station; // 각 회차에서의 출발 역
	int *desti_station; // 각 회차에서의 도착 역
	int start_line_index; // 출발역의 호선번호. 역 번호를 계산하기 위해 쓰인다
	int start_station_index; // 출발역의 역 고유 번호
	int desti_line_index; // 도착역의 호선번호, 역 번호를 계산하기 위해 쓰인다
	int desti_station_index; // 도착역의 역 고유 번호
	void init(){
	int temp;
	fin >> tot_lines;
	num_of_line = new int [tot_lines + 1];
	num_of_line[0] = 0;
	for(int i = 1; i <= tot_lines; i++){
	fin >> num_of_line[i];
	fin >> num_of_line[i];
	}
	for(int j = 1; j <= tot_lines; j++){
	tot_stations += num_of_line[j];
	}
	subway_map = new int *[tot_stations + 1];
	for(int k = 0; k <= tot_stations; k++){
	subway_map[k] = new int [tot_stations + 1];
	}
	fin >> tot_trans;
	fr_trans_station = new int [tot_trans];
	to_trans_station = new int [tot_trans];
	for(int l = 0; l < tot_trans; l++){
	fin >> line_index;
	fin >> station_index;
	for(int m = 0;m < line_index; m++){
	temp = num_of_line[m];
	station_index = temp + station_index;
	}
	fr_trans_station[l] = station_index;
	fin >> line_index;
	fin >> station_index;
	for(int n = 0; n < line_index; n++){
	temp = num_of_line[n];
	station_index = temp + station_index;
	}
	to_trans_station[l] = station_index;
	}
	fin >> phase;
	transfer_time = new int [phase];
	start_station = new int [phase];
	desti_station = new int [phase];
	for(int o = 0; o < phase; o++){
	fin >> transfer_time[o];
	fin >> start_line_index;
	fin >> start_station_index;
	start_station[o] = start_station_index;
	for(int p = 0; p < start_line_index; p++){
	temp = num_of_line[p];
	start_station[o] = temp + start_station[o];
	}
	fin >> desti_line_index;
	fin >> desti_station_index;
	desti_station[o] = desti_station_index;
	for(int q = 0; q < desti_line_index; q++){
	temp = num_of_line[q];
	desti_station[o] = temp + desti_station[o];
	}
	}
	}
	void make_map(int trans_time){
	int temp;
	int border = 0;
	for(int i = 0; i <= tot_stations; i++){
	for(int j = 0; j <= tot_stations; j++){
	subway_map[i][j] = INFINITE;
	}
	}
	for(int k = 1; k <= tot_stations; k++){
	if((k - 1) > 0)
	subway_map[k][k-1] = 1;
	subway_map[k][k] = 0;
	if((k + 1) <= tot_stations)
	subway_map[k][k+1] = 1;
	}
	for(int l = 0; l < tot_trans; l++){
	subway_map[fr_trans_station[l]][to_trans_station[l]] = trans_time;
	subway_map[to_trans_station[l]][fr_trans_station[l]] = trans_time;
	}
	for(int m = 1; m < tot_lines; m++){
	temp = num_of_line[m];
	border = temp + border;
	subway_map[border][border+1] = INFINITE;
	subway_map[border+1][border] = INFINITE;
	}
	}
	int path_finder(int phase_num){
	int *length;
	int *length_mirror;
	length = new int [tot_stations + 1];
	length_mirror = new int [tot_stations + 1];
	int start, desti,duration;
	int min;
	int i, vnear;
	int stat = 1;
	start = start_station[phase_num];
	desti = desti_station[phase_num];
	for(i = 0; i <= tot_stations; i++){
	length[i] = subway_map[start][i];
	length_mirror[i] = subway_map[start][i];
	}
	while(stat <= tot_stations){
	min = INFINITE;
	for(i = 0; i <= tot_stations; i++){
	if((0 <= length[i]) && (length[i] < min) && (i != start)){
	min = length[i];
	min = length_mirror[i];
	vnear = i;
	}
	}
	for(i = 0; i <= tot_stations; i++){
	if(length[vnear] + subway_map[vnear][i] < length[i]){
	length[i] = length[vnear] + subway_map[vnear][i];
	length_mirror[i] = length_mirror[vnear] + subway_map[vnear][i];
	}
	}
	length[vnear] = -1;
	stat++;
	}
	duration = length_mirror[desti];
	delete [] length;
	delete [] length_mirror;
	return duration;
	}
	int main(){
	init();
	if(tot_lines > MAX_LINES){
	cout << "Too much lines!" <<endl;
	return 0;
	}
	for(int i = 1; i <= tot_lines; i++){
	if(num_of_line[i] > MAX_STATION){
	cout << "Too much stations!" <<endl;
	return 0;
	}
	}
	for(int j = 0; j < phase; j++){
	make_map(transfer_time[j]);
	cout << path_finder(j) << endl;
	}
	delete [] num_of_line;
	delete [] fr_trans_station;
	delete [] to_trans_station;
	delete [] transfer_time;
	delete [] start_station;
	delete [] desti_station;
	for(int k = 0; k < (tot_stations + 1); k++){
	delete [] subway_map[k];
	}
	delete [] subway_map;
	return 0;
	}

view raw dijkstra_shortest_path.cpp hosted with ❤ by GitHub