•
문제
거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.
각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.
풀이
•
기본 알고리즘
1. 다익스트라를 한번 수행하여 최단경로를 구한다.
2. 구한 최단경로를 원래 그래프에서 제외한다.
3. 다익스트라를 다시 한 번 수행한다.
C++
복사
•
dijkstra 함수
•
기존 다익스트라 알고리즘을 활용하여 최단 경로를 구한다.
•
2번째 다익스트라에서는 갈 수 없는 edge 조건이 추가된다.
void dijk(int start) {
priority_queue<pair<int, int>> q;
q.push({ 0, start });
dist[start] = 0;
while (!q.empty()) {
int cost = -q.top().first;
int cur_node = q.top().second;
q.pop();
if (cost > dist[cur_node]) continue;
for (auto next : graph[cur_node]) { //현재 노드에 연결된 엣지들
int next_cost = cost + next.second;
int next_node = next.first;
if (next.second == -1) continue; //사용할 수 없는 엣지 (2번째 다익스트라에서 활용)
if (next_cost < dist[next_node]) {
dist[next_node] = next_cost;
q.push({ -next_cost, next_node });
path[next_node].clear(); //최단거리가 갱신되는 경우엔 이전 path 초기화
path[next_node].push_back(cur_node); //경로를 저장하기 위한 path vector
}
else if (next_cost == dist[next_node]) {
path[next_node].push_back(cur_node); //같은 경우엔
}
}
}
}
C++
복사
•
RemovePath 함수
•
A,C,D → B의 최단 경로인 경우 path[B] = A,C,D 형태로 역순으로 입력되어 있다.
•
따라서 도착노드 B를 선택하고, B로 올 수 있는 A,C,D 후보군에 대해 A → B , C → B, D → B 경로를 없애준다.
•
연결된 모든 경로를 탐색하는 BFS 알고리즘을 활용한다.
void findpath(int start, int end) {
queue<int> temp;
bool visit[MAX] = { 0 };
temp.push(end);
while (!temp.empty()) {
int next_node = temp.front();
temp.pop();
if (next_node == start) continue; //시작점이라면 더이상 고려하지 않음
for (int i = 0; i < path[next_node].size(); i++) { // B로 올 수 있는 Node들에 대해
int prev_node = path[next_node][i]; // B로 갈 수 있는 특정 노드
if (visit[prev_node]) continue; // 기존에 이미 처리되었다면 패스
for (int j = 0; j < graph[prev_node].size(); j++) { // B로 갈수 있는 Node의 edge탐색
if (graph[prev_node][j].first == next_node) { // 목적지가 B(찾았다 원하는 edge!)
graph[prev_node][j].second = -1; // 해당 Edge 없애기
break;
}
}
temp.push(prev_node);
}
visit[next_node] = 1;
}
}
C++
복사
•
Main 동작
•
기본 풀이 알고리즘대로 다익스트라 → 최단경로 제거 → 다익스트라 를 수행한다.
int main() {
fastio;
int N, M, S, D, U, V, P; // N - 장소의 수, M-도로의 수, S- 시작점, D - 도착점 , UVP - 도로 정보 (U -> V 도로 길이 P)
while (1) {
cin >> N >> M;
if (N == 0 && M == 0) break;
cin >> S >> D;
// 초기화
for (int i = 0; i < N; i++) {
dist[i] = 1e9;
graph[i].clear();
}
for (int i = 0; i < M; i++) {
cin >> U >> V >> P;
graph[U].push_back({ V,P });
}
dijk(S);
findpath(S, D); // 최단 경로 지우기
for (int i = 0; i < N; i++) { // 다익스트라를 다시 한 번 사용하므로 거리 초기화 필요
dist[i] = 1e9;
}
dijk(S);
if (dist[D] == 1e9) cout << -1 << '\n';
else cout << dist[D] << '\n';
}
return 0;
}
C++
복사
중요
•
다익스트라 알고리즘에서 단순 최단거리를 구하는 것 뿐만 아니라 최단 경로까지 구해야 하는 경우의 활용법을 기억해두자
•
만약 하나의 최단 경로만이 존재하는 경우엔 vector를 클리어하면서 여러개의 경로를 같이 고려하지 않고 단순히 이전 Node만 저장하는 방법도 사용 가능하다.
void dijk(int start) {
priority_queue<pair<int, int>> q;
q.push({ 0, start });
dist[start] = 0;
while (!q.empty()) {
int cost = -q.top().first;
int cur_node = q.top().second;
q.pop();
if (cost > dist[cur_node]) continue;
for (auto next : graph[cur_node]) { //현재 노드에 연결된 엣지들
int next_cost = cost + next.second;
int next_node = next.first;
if (next.second == -1) continue; //사용할 수 없는 엣지 (2번째 다익스트라에서 활용)
if (next_cost < dist[next_node]) {
dist[next_node] = next_cost;
q.push({ -next_cost, next_node });
path[next_node].clear(); //최단거리가 갱신되는 경우엔 이전 path 초기화
path[next_node].push_back(cur_node); //경로를 저장하기 위한 path vector
}
else if (next_cost == dist[next_node]) {
path[next_node].push_back(cur_node); //같은 경우엔
}
}
}
}
C++
복사
