BOJ 2325) c++ 개코전쟁

시간 제한 - 2s

메모리 제한 - 256MB

 

---

풀이

1. 최단경로가 최대가 되기 위해서는 최단경로를 끊어야한다. 최단경로가 아닌 간선을 끊어봐야 최단경로는 그대로이기 때문

2. 최단경로를 구해, 해당 경로에서 거치는 노드를 하나씩 끊고, 다시 최단경로를 구하는 방식으로 최대 값을 구한다.

3. 최단 경로가 여러 개일 때, 현재의 최단 경로만 확인하는게 의미가 있는지?

그림 1) 최단거리가 5인 여러가지 간선이 있는 상황

    3.1) 동일한 최단경로가 없을 때(A->B)

        - A->B가 최단경로이므로, A->B를 끊으면 A->C->B로 최단경로가 1 늘어나며 A-C, C->B 등 최단경로 이외의 간선을 끊어도 결과는 A->B로 같은 걸 확인할 수 있음

    3.2) 동일한 최단 경로가 중복되지 않는 경로로 존재할 때(A->G)

        - A->B->D->G 또는 A->C->E->D->G, A->F->G의 최단거리가 같음, 이 상황에서 어떤 간선을 끊던 기존 최단 경로는 변하지 않으므로 하나의 최단 경로를 통해 확인 가능(최단거리1, 최단거리2 => 최단거리1(이제 아님), 최단거리2)

    3.3) 동일한 최단 경로가 중복되는 경로로 존재할 때

        - A->D->G까지 경로에서 중복되지 않는 A->D 구간은 3.2의 방식으로 생각해 A->D의 어느 간선을 끊던 결과가 같음이 증명됨. 중복되는 D->G 구간이 의미있는 간선제거가 이루어짐

        - 만일 D->G의 제거 이후에도 최단 경로가 같다면 어떤 간선을 끊던 결과가 변하지 않음이 증명되고,

        - D->G 제거 이후에 최단 경로가 변한다면 의미있는 간선 제거가 이루어진 것.

 

결과적으로 여러 최단경로가 존재할 때, 제거해야하는 간선은 여러 최단경로 사이에 중복되어 존재하거나, 제거할 필요가 없기 때문에 최단 경로가 여러 개라도 하나의 최단경로에서 결과를 얻을 수 있음

 

입력

정점의 갯수 N, 간선의 갯수 M이 입력됨

 

자료구조

정점간의 인접행렬을 담을 2차원 배열,

시작점부터 특정 정점까지의 최단거리를 기록할 Dp배열,

최단경로를 구하는 동안, 이전의 출발 지점을 기록할 Path map(map[now] = prev_node 형태로 저장)

 

로직

1. 최단 거리를 구하고, 최단거리에 속하는 경로를 순회

2. 최단거리 사이의 간선을 하나씩 제거하며 최단거리를 구해 차이 확인

---

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace		std;
using pii=pair<int,int>;
using edg=pair<int,pii>;

vector<vector<pii>>	grp;
vector<int>	 		 dp;
map<int, int>		path;
int			n, m, x, y, z, q = -1, w = -1;

void dijkstra() {
	priority_queue<edg, vector<edg>, greater<edg>> pq;	//	pii < cost, < prev, next > >

	pq.push(edg(0, pii(1, 1)));
	while (!pq.empty()) {
		const pii& edge = pq.top().second;
		const int cost = pq.top().first, prev = edge.first, now = edge.second;
		pq.pop();

		if (dp[now] > cost) {
			dp[now] = cost;
			path[now] = prev;
			for (auto& beg : grp[now]) {
            	//	제거된 간선이라면 스킵
				if ((beg.first == q && now == w) || (beg.first == w && now == q)) continue ;
				if (dp[beg.first] > cost + beg.second) pq.push(edg(cost + beg.second, pii(now, beg.first)));
			}
		}
	}
}

int answer() {
	vector<int> paths;
	fill(dp.begin(), dp.end(), 987654321);
	dijkstra();
	int i = n;
	while (true) {	//	맵의 경로를 배열에 담아 사용
		paths.push_back(i);
		if (i == path[i]) break ;
		i = path[i];
	}

	int ret = dp[n];
	for (int i = 0; i < paths.size() - 1; i++) {
		fill(dp.begin(), dp.end(), 987654321);
		q = paths[i]; w = paths[i + 1];
		dijkstra();
		ret = max(ret, dp[n]);
	}
	return ret;
}

int main() {

	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;
	grp.resize(n + 1);
	dp.resize(n + 1);

	while (m--) {
		cin >> x >> y >> z;
		grp[x].push_back(pii(y, z));
		grp[y].push_back(pii(x, z));
	}
	cout << answer() << endl;
	return 0;
}

 

시간 복잡도

모든 간선을 전부 제거하며 확인 시, O(간선의 수 * (V + E)logV)이나,

최단 경로를 구해 필요한 간선만 확인 시 O(정점의 수 * (V + E)logV)이므로 M(V+E)logV => N(V+E)logV로 최대 1000배 시간복잡도 감소