7. 최단 경로 알고리즘 - 선거 공약(promises) 문제

문제를 해결하기 위해 각 도시를 정점으로 하고 고속도로를 간선으로 하는 그래프를 모델링 할 수 있다.

현재 존재하는 고속도로들에 대해서 플로이드 알고리즘을 실행하여 각 도시간 최단 경로를 구한다.

그 후 새로 건설할 고속도로를 첫번째부터 두 도시를 잇는 경로의 최단 시간을 비교하게 된다.

새로 건설할 고속도로가 최단 시간이 더 짧으면 해당 고속도로를 건설하고, 현재 고속도로의 최단 시간이 더 짧거나 같으면 건설하지 않는다.

이 때 새로 건설한 고속도로에 대해서 그래프를 업데이트 해주어야 한다.

그런데 고속도로를 새로 건설할 때마다 기존 플로이드 알고리즘을 한번 더 수행해 주는 것은 매우 비효율적이다.

새로 건설한 고속도로가 연결하는 도시가 a와 b라고 하자.

그러면 두 도시간 최단 경로에 변경이 생기는 경우는 a나 b를 경유점으로 가지는 경로가 될 것이다.

따라서 a와 b에 대해서만 경유점 집합을 구성하여 플로이드 알고리즘을 수행하도록 한다.

그러면 O(2*|V|*|V|) 시간 만에 그래프를 업데이트 할 수 있다.

// 선거 공약 문제를 해결하는 플로이드 알고리즘

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int INF = 987654321;

int adj[200][200];  // 그래프의 인접 행렬

vector< vector<int> > future;  // 앞으로 건설될 고속도로 목록

void floyd(int v) {

for (int i = 0; i < v; i++) {

adj[i][i] = 0;

}

for (int k = 0; k < v; k++) {

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++) {

adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

}

}

}

}

void update(int order, int v) {

int a = future[order][0];

int b = future[order][1];

int cost = future[order][2];

adj[a][b] = cost;

adj[b][a] = cost;

for (int k = 0; k < 2; k++) {  // a와 b만 경유점 집합에 포함 시킨다.

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++) {

adj[i][j] = min(adj[i][j], adj[i][future[order][k]] + adj[future[order][k]][j]);

}

}

}

}

int main() {

int c;  // 테스트 케이스 수

vector<int> result;

cin >> c;

for (int test = 0; test < c; test++) {

int v, m, n;  // 도시의 수와 현재 존재하는 고속도로의 수, 앞으로 건설될 고속도로의 수

cin >> v >> m >> n;

// 인접 행렬의 값을 아주 큰 값으로 초기화

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++) {

adj[i][j] = INF;

}

}

for (int i = 0; i < m; i++) {

int a, b, c;

cin >> a >> b >> c;

if (adj[a][b] > c) adj[a][b] = c;

if (adj[b][a] > c) adj[b][a] = c;

}

for (int i = 0; i < n; i++) {

vector<int> input(3);

cin >> input[0] >> input[1] >> input[2];

future.push_back(input);

}

floyd(v);

int res = 0;

for (int i = 0; i < n; i++) {

int a = future[i][0];

int b = future[i][1];

int cost = future[i][2];

// 현재 고속도로 상에서 a에서 b로 가는 시간보다 새로 지을 고속도로 시간이 더 적으면

if (cost < adj[a][b]) {  

// 고속도로를 건설한다.

update(i, v);

}

else {

// 새로 건설할 의미가 없으면 res값을 하나 증가한다.

res++;

}

}

result.push_back(res);

future.clear();

}

for (int i = 0; i < c; i++) {

cout << result[i] << endl;

}

return 0;

}

간선의 집합을 늘려가는 플로이드 알고리즘

플로이드 알고리즘을 약간 변형하여 다른 방법으로도 문제를 해결할 수 있다.

경유할 수 있는 정점의 집합을 늘려가는 대신 간선의 집합을 늘려가는 것이다.

간선의 집합 E를 경유할 수 있을 때 u에서 v로 가는 최단 거리를 De(u, v) 라고 하자.

이 때 E의 원소 중 간선 (a, b) 가 있을 때 다음 점화식을 만족한다.

De(u, v) = min(De'(u, v), De'(u, a) + w(a, b) + De'(b, v), De'(u, b) + w(b, a) + De'(a, v))

이때 E'는 E-{(a,b)} 를 의미한다.

간선은 어느 방향으로 타고 갈 것인가를 정해야 하기 때문에 경우의 수가 세개로 늘어난 것을 볼 수 있다.

이 점화식을 활용하면 새로운 고속도로를 건설했을 때 해당 간선을 경유할 경우에 대해서만 업데이트를 해주면 된다.

// 새 간선이 추가되었을 때 최단거리 갱신하기

int v;

int adj[200][200];

bool update(int a, int b, int c){

// 새로 건설할 의미 없을 때 false 리턴

if(adj[a][b] <= c) return false;

for(int i = 0; i < v; i++){

for(int j = 0; j < v; j++){

adj[i][j] = min(adj[i][j], min(adj[i][a] + c + adj[b][j], adj[i][b] + c + adj[a][j]));

}

}

return true;

}