문제 : 지하철에서 최단 경로 구하기
지하철에서 두 역 간의 최단 시간 경로를 구하는 데 다음을 가정한다.
1. 지하철은 n(n <= 10)개의 노선이 있다, I 번째 노선의 역 이름은 제일 왼쪽 역부터 I-1, I-2, I-3 .......으로 주어진다. 각 노선별 역의 수는 50보다 작거나 같다.
2. 역과 역사이의 운행시간은 모두 1로 한다.
3. 지하철 환승은 두 개의 서로 다른 노선사이에서만 환승한다. 그러므로 환승역은 두 개의 역 이름이 주어 진다 (예 : 1-5, 2-3). 환승 시간 t는 입력으로 주어진다.
4. 지하철-버스 환승은 두 개의 역 사이에서 환승한다. 즉, 역-버스-역이다. 환승 시간 + 버스 운행 시간 s는 입력으로 주어진다.
5. 출발역과 도착역은 환승역이 아니라고 가정한다.
입력
입력 파일의 이름은 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 /* 버스 환승의 수
1 3 3 6 7 /* 1-3번역과 3-6번역 s=7
1 7 2 11 5
3 /* 테스트할 데이터의 수
0 2 2 3 14 /* t=0 , 2-2번역에서 출발 3-14번역에 도착
5 1 3 2 4 /* t=5 , 1-3번역에서 출발 2-4번역에 도착
3 1 1 3 7 /* t=3 , 1-1번역에서 출발 3-7번역에 도착
출력
출력은 다음과 같은 형식으로 한다.
9 /* 첫 번째 데이터의 최단 경로 시간
8 /* 두 번째 데이터의 최단 경로 시간
10 /* 세 번째 데이터의 최단 경로 시간
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
// MAX 값은 노선 * 해당 노선의 역의 수 = 500에서, 여유있게 1000으로 설정.
#define MAX 1000
using namespace std;
// 환승 코스트가 고려되지않은 원본 그래프
vector<pair<int, int>> graph[MAX]; //{destination, weight}
// 환승 정보 벡터
vector<int> transferInfo;
// 호선별 역의 수
vector<int> stationNum;
// 환승 역의 인덱스
vector<pair<int, int>> transferIndex;
// 가중치용 임시그래프
vector<pair<int, int>> tmpGraph[MAX];
// 가중치에 따라(즉, 테스트케이스에 따라) 임시그래프를 clear 및 교체한다.
void ResetGraphByTransferStation(int weight){
for (int i = 0; i < MAX; i++) {
tmpGraph[i].clear();
tmpGraph[i] = graph[i];
}
// 지하철역 환승 cost에 따라 graph 수정.
for (int i = 1; i < transferIndex.size(); i++) {
tmpGraph[transferIndex[i].first].push_back(make_pair( transferIndex[i].second, weight ));
tmpGraph[transferIndex[i].second].push_back(make_pair( transferIndex[i].first, weight ));
}
}
// 호선과 역의 변수 값에 따라 마킹을 해야하는 인덱스를 반환.
int CalcStartingIndex(int line, int station) {
int startPoint = 0;
for (int k = 1; k < line; k++) {
startPoint += stationNum[k];
}
// startPoint는 현재 환승역의 index를 가지고 있게 됨.
startPoint += station;
return startPoint;
}
int FindShortestPath(int start, int target, int vertex) {
//start를 기준으로 거리를 저장. 가중치는 INF(987654321)로 가정.
vector<int> distance(vertex+1, 987654321);
// 자신에게 가는 비용은 0임.
distance[start] = 0;
// {정점, 비용} pair의 최소 우선순위 큐 생성.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
//초기 비용과 시작점
pq.push(make_pair( 0, start ));
while (!pq.empty())
{
int cost = pq.top().first;
int nowVertex = pq.top().second;
pq.pop();
//최소거리가 아닌경우.
if (distance[nowVertex] < cost)
continue;
//인접 노드들 전부 확인
for (int i = 0; i < tmpGraph[nowVertex].size(); i++)
{
int neighbor = tmpGraph[nowVertex][i].first;
int neighborDistance = cost + tmpGraph[nowVertex][i].second;
//최소 경로 발견시 업데이트
if (distance[neighbor] > neighborDistance)
{
distance[neighbor] = neighborDistance;
pq.push(make_pair( neighborDistance, neighbor ));
}
}
}
// 원하는 지하철 역(타겟) 까지의 최단거리 반환.
return distance[target];
}
int main() {
ifstream inFile("input.txt");
// 지하철 정보 입력.
int lineNum;
inFile >> lineNum;
stationNum.push_back(0);
// 예제의) 1호선 1~14, 2호선 15~28, 3호선 29~44로 인덱싱.
// 1번째 역부터 인덱스 시작.
int index = 1;
for (int i = 1; i <= lineNum; i++) {
int line = 0, station = 0;
inFile >> line >> station;
stationNum.push_back(station);
// 현재의 인덱스 번호, 이는 아래 for문에서 index 만큼의 수를 더 돌기 위함.
int nowIndex = index - 1;
for (int j = index; j < station + nowIndex; j++) {
// 지하철은 양방향 그래프라 2개 추가
graph[index].push_back(make_pair(j + 1 , 1 ));
graph[index + 1].push_back(make_pair(j, 1 ));
index++;
}
// 현재 호선의 지하철역 숫자가 끝났을 경우 index 증가.
index++;
}
// 환승 역 정보 입력
int transferStation;
inFile >> transferStation;
transferIndex.push_back(make_pair(0,0 ));
for (int i = 0; i<transferStation; i++) {
int line1, station1, line2, station2;
inFile >> line1 >> station1 >> line2 >> station2 ;
// 환승해야 할 역의 그래프 내 인덱스를 푸시.
transferIndex.push_back(make_pair(CalcStartingIndex(line1, station1), CalcStartingIndex(line2, station2) ));
}
// 버스 환승 정보 입력. 그래프에 간선을 추가해 주어야 한다.
int busTransferNum;
inFile >> busTransferNum;
// 그래프에 버스환승 엣지 추가.(양방향)
for (int i = 0; i < busTransferNum; i++) {
int line1, station1, line2, station2, weight;
inFile >> line1 >> station1 >> line2 >> station2 >> weight;
int startPoint_1 = CalcStartingIndex(line1, station1);
int startPoint_2 = CalcStartingIndex(line2, station2);
graph[startPoint_1].push_back(make_pair(startPoint_2, weight ));
graph[startPoint_2].push_back(make_pair(startPoint_1, weight ));
}
// 다익스트라 실행 및 데이터 출력부
int testNum;
inFile >> testNum;
// 현재 총 지하철 역의 개수
int vertexNum = 0;
for (int i = 0; i < stationNum.size(); i++) {
vertexNum += stationNum[i];
}
// 결과를 저장할 집합.
vector<int> resultSet;
// 테스트케이스 시작.
for (int i = 0; i < testNum; i++) {
int transferCost, startLine1, startStation1, startLine2, startStation2;
inFile >> transferCost >> startLine1 >> startStation1 >> startLine2 >> startStation2;
// 그래프 초기화
ResetGraphByTransferStation(transferCost);
// 시점 ~ 종점으로 가는 최단거리 찾고, 결과 집합에 저장.
resultSet.push_back(FindShortestPath(CalcStartingIndex(startLine1, startStation1), CalcStartingIndex(startLine2, startStation2), vertexNum));
}
// 결과 출력
for (int i = 0; i < resultSet.size(); i++) {
cout << resultSet[i] << endl;
}
}
| cs |
댓글
댓글 쓰기