[BOJ]5719 거의 최단 경로

[정답이 아니라 풀이 기록입니다.]

거의 최단 경로

유향그래프가 있다. s노드에서 e노드로 가는 최단 경로들이 있을때, 이 경로의 간선들을 이용하지 않는 최단 경로를 거의 최단 경로라고 한다. 거의 최단 경로의 길이를 구하여라

접근

1. 최단 경로가 여러개라면 최단 경로들을 이루는 모든 간선을 이용 할 수 없습니다.
2. 거의 최단 경로가 없을 수도 있습니다.
3. 거의 최단 경로도 여러개 있을 수 있습니다.
4. 최단경로, 거의 최단 경로 둘다 없을 수도 있습니다.

구현

최단 거리 구하기

최단 거리는 다익스트라를 통해서 구하면 되고
최단 거리와 노드를 같이 저장해야하기에 pair로 저장해야합니다.

STL 다익스트라는 큰것이 위로 올라오는 특성이 있기에 아래와 같이 선언해서 작은 것이 위로 올라오게 해줍니다.

priority_queue<pair<long long,long long>,vector<pair<long long, long long>>
	,greater<pair<long long, long long>>> pq;

일단 기본 다익스트라를 만들어 봅니다.

pq.push({0LL,s});
while (!pq.empty()) {
		long long value = pq.top().first;
		int node = pq.top().second;
		pq.pop();

		if (value > D[node]) {
				continue;
		}
		for (int i = 0; i < v[node].size(); i++) {
				if (D[v[node][i].first] > value + v[node][i].second) {
					D[v[node][i].first] = value + v[node][i].second;
					pq.push({ D[v[node][i].first] ,v[node][i].first });
				}
		}
}

그리고 이 문제에서는 최단 경로를 역추적해서 간선을 제거해야하기에 어떤 노드에서 갱신이 되었는지 기록해둬야 합니다

a노드에서 b노드가 갱신되었다
->시작점에서 b노드까지 올때 a를 통해 오는게 최단 경로이다.
이후에 만약 b가 도착지 노드를 갱신시킨다면?
->b는 도착지까지 가는 최단경로에 포함되고 b까지 오는 최단경로인 a도 포함된다.

기록과 제거는 대략적으로 위와 같이 이루어지는데 제거는 좀 이따 보기로하고 기록부터 보겠습니다.

기록

위에서 이야기했듯 a노드에서 b노드가 갱신되었다는 것은 시작점에서 b노드까지 올때 a를 통해 오는게 최단 경로이다는 것 입니다.

그리고 b지점까지 오는 최단 경로는 여러개 있을 수 있습니다.
그렇다면 b의 최단거리를 갱신시키는 노드는 1개지만, 최단거리가 같은 노드가 여러개 있을 수 있습니다.

시작점에서 a거쳐서 b = 10의 거리
시작점에서 c거쳐서 b = 10의 거리
이 경우 a,c 둘 다 최단 경로를 구성함

그렇기에 갱신의 기록은 컨테이너에 기록해야합니다.
저는 큐를 사용하였습니다.

만약 갱신이 일어난다면 이전의 기록은 필요 없기에 큐를 초기화하고 큐에 추가하고
최단거리가 같은 값이 들어온다면 큐에 추가해주는 방식입니다.

pq.push({0LL,s});
while (!pq.empty()) {
		long long value = pq.top().first;
		int node = pq.top().second;
		pq.pop();

		if (value > D[node]) {
				continue;
		}
		for (int i = 0; i < v[node].size(); i++) {
				if (D[v[node][i].first] > value + v[node][i].second) {
					D[v[node][i].first] = value + v[node][i].second;
					while (!check[v[node][i].first].empty()) {
						check[v[node][i].first].pop();
					}
					check[v[node][i].first].push(node);
					pq.push({ D[v[node][i].first] ,v[node][i].first });
				}
				else if (D[v[node][i].first] == value + v[node][i].second) {
					check[v[node][i].first].push(node);
				}
		}
}

역추적과 간선 제거

만약 시작점과 도착점이 연결되어있다면 기록을 하는 큐에 마치 그래프처럼 최단경로들로 연결이 되어 있을 것입니다.
그렇기에 도착점부터 시작점 방향으로 역추적을 하며 간선을 제거합니다

1. 도착노드의 큐를 확인
2. 큐에 있는 노드들을 a,b,c라 했을 때, a->도착지, b->도착지,c->도착지 간선을 제거 후
3. a,b,c노드로 이동해 반복해서 확인

이런식으로 BFS와 같이 움직이며 제거합니다.

void del(int node) {
	int top;
	while (!check[node].empty()) {
		 top = check[node].front();
		 check[node].pop();
		 //제거
		 del(top);
	}
}

기본 코드는 위와 같습니다.
여기서 이제 top->node 간선을 제거해야합니다.

v[top]에서 lower_bound를 돌려 top->node 간선을 찾아내고 이를 erase로 제거하는 방식을 사용합니다.

bool comp(const pair<long long, long long> &a,const  pair<long long, long long> &b) {
	return a.first<b.first;
}

v[top].erase(lower_bound(v[top].begin(),v[top].end(),pair<long long, long long>(node,0),comp));

(벡터가 pair로 이루어져있기에 비교함수를 커스텀해야합니다.)

제거의 전체적인 코드는 아래와 같습니다.

bool comp(const pair<long long, long long> &a,const  pair<long long, long long> &b) {
	return a.first<b.first;
}

void del(int node) {
	int top;
	while (!check[node].empty()) {
		 top = check[node].front();
		 check[node].pop();
		 v[top].erase(lower_bound(v[top].begin(),v[top].end(),
         		pair<long long, long long>(node,0),comp));
		 del(top);
	}
}

거의 최단 거리 구하기

일반 다익스트라로 최단거리를 구하면 됩니다.
최단 경로를 이루는 간선을 제거했기에 그냥 다익스트라로 구해지는 경로가 거의 최단 경로입니다.

pq.push({ 0LL,s });
while (!pq.empty()) {
			long long value = pq.top().first;
			int node = pq.top().second;
			pq.pop();

			if (value > AlmostD[node]) {
					continue;
			}
			for (int i = 0; i < v[node].size(); i++) {
					if (AlmostD[v[node][i].first] > value + v[node][i].second) {
						AlmostD[v[node][i].first] = value + v[node][i].second;
						pq.push({ AlmostD[v[node][i].first] ,v[node][i].first });
					}
			}
	}

답출력

최단 경로가 없다면 거의 최단 경로도 있을 수 없습니다.
그렇기에 D[도착지]가 INF라면 -1을 출력합니다.

D[도착지]가 INF가 아닐경우
AlmostD[도착지]가 INF라면 -1, 아니라면 AlmostD[도착지]를 출력하면 됩니다.

이것을 테스트 케이스마다 반복하면 되는데 벡터의 초기화, D,AlmostD의 초기화,큐의 초기화에 유의해야합니다.

마무리

역추적과 간선의 삭제가 복잡한 편입니다.

끝