[P5] 백준 2325번 개코전쟁 C++ 다익스트라, 역추적

리뷰

 

https://www.acmicpc.net/problem/2325

처음엔 간선 사용 여부를 DP로 사용해야하나 고민했지만, 역추적을 통해 경로 중 하나의 간선을 제거했을때 최적해를 보장해야 한다는 결론을 지었다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 인접 리스트를 저장할 Edge타입 벡터 배열
• Pos : 현재 위치와 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.
• Path : 간선의 양쪽 노드를 정의할 구조체

 

함수

1. get_path

vector<Path> get_path() {
	priority_queue<Pos> pq;
	pq.push({ 1, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[1] = 0;
	vector<int> prev(n + 1);

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cv = pos.v;
		if (dist[cx] < cv) continue;
		if (cx == n) break;

		for (const Edge& edge : edges[cx]) {
			int nx = edge.y, nv = cv + edge.z;

			if (dist[nx] > nv) {
				dist[nx] = nv;
				prev[nx] = cx;
				pq.push({ nx, nv });
			}
		}
	}

	vector<Path> paths;
	int cur = n;
	while (cur != 1) {
		paths.push_back({prev[cur], cur});
		cur = prev[cur];
	}
	return paths;
}

 

도로를 제거하기 전 최단 경로에서 사용된 간선 정보를 구하기 위한 함수

 

2. dijkstra

int dijkstra(int f, int t) {
	priority_queue<Pos> pq;
	pq.push({ 1, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[1] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cv = pos.v;
		if (dist[cx] < cv) continue;
		if (cx == n) return cv;

		for (const Edge& edge : edges[cx]) {
			int nx = edge.y, nv = cv + edge.z;
			if (cx == f && t == nx) continue;
			if (nx == f && t == cx) continue;

			if (dist[nx] > nv) {
				dist[nx] = nv;
				pq.push({ nx, nv });
			}
		}
	}
	return -1;
}

 

특정 간선을 제거한 상태에서의 1->N까지의 최단 시간을 구하기 위한 함수

 

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 edges에 양방향 간선을 추가하여 인접리스트를 초기화한다.
2. Path타입 벡터 paths에 get_path함수를 호출하여 얻은 최단 경로에서 사용한 간선을 저장한다.
3. 변수 mx를 0으로 초기화하고, paths의 내부 요소를 순회한다.
4. 매 루프마다 변수 f, t에 간선의 양 끝 노드의 번호를 저장한다.
5. dijkstra함수에 f, t를 전달해 해당 노드를 끝점으로 하는 간선을 사용하지 않으면서 1->N으로 이동 가능한 최단 시간과 기존의 mx중 더 큰 수를 mx에 저장한다.
6. 모든 탐색을 마친 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 두 정점사이에는 두 개 이상의 길이 존재하지 않고 모든 도로는 양방향이며 한 도로를 파괴하는 것은 양방향의 길 모두를 파괴하는 것이다.
2. 첫 다익스트라에서 확인한 최단 경로 외에 동일한 시간을 갖는 최단 경로가 존재할 수 있다.
3. 이 경우엔 간선 하나를 제거한다고 하더라도 이미 다른 최적의 경로가 또 있는 것이므로 어차피 어떤 간선을 제거하더라도 기존의 최단 경로와 동일하다.
4. 최대 N-1개의 간선을 순회할 수 있다. 그러므로 첫 다익스트라 포함 최대 N번의 다익스트라가 수행될 수도 있다. 이는 시간적으로 무리가 없다고 판단했다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 1e3 + 1;
int n, m;
struct Edge {
	int y, z;
};
vector<Edge> edges[N];
struct Pos {
	int x, v;
	bool operator<(const Pos& other) const {
		return v > other.v;
	}
};
struct Path {
	int f, t;
};

vector<Path> get_path() {
	priority_queue<Pos> pq;
	pq.push({ 1, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[1] = 0;
	vector<int> prev(n + 1);

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cv = pos.v;
		if (dist[cx] < cv) continue;
		if (cx == n) break;

		for (const Edge& edge : edges[cx]) {
			int nx = edge.y, nv = cv + edge.z;

			if (dist[nx] > nv) {
				dist[nx] = nv;
				prev[nx] = cx;
				pq.push({ nx, nv });
			}
		}
	}

	vector<Path> paths;
	int cur = n;
	while (cur != 1) {
		paths.push_back({prev[cur], cur});
		cur = prev[cur];
	}
	return paths;
}

int dijkstra(int f, int t) {
	priority_queue<Pos> pq;
	pq.push({ 1, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[1] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cv = pos.v;
		if (dist[cx] < cv) continue;
		if (cx == n) return cv;

		for (const Edge& edge : edges[cx]) {
			int nx = edge.y, nv = cv + edge.z;
			if (cx == f && t == nx) continue;
			if (nx == f && t == cx) continue;

			if (dist[nx] > nv) {
				dist[nx] = nv;
				pq.push({ nx, nv });
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		int x, y, z; cin >> x >> y >> z;
		edges[x].push_back({ y, z });
		edges[y].push_back({ x, z });
	}

	vector<Path> paths = get_path();
	int mx = 0;
	for (const Path& path : paths) {
		int f = path.f, t = path.t;
		mx = max(mx, dijkstra(f, t));
	}
	cout << mx;
}