[G1] 백준 2307번 도로검문 C++ 다익스트라, 경로 역추적

리뷰

 

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

최소힙을 구현해야하는데 최대힙을 구현해서 한번 틀려먹었다.

 

 

전역 변수

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

 

함수

1. f_dijkstra

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

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

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

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

	vector<pair<int, int>> path;
	int cn = n;
	while (cn != 1) {
		path.push_back({ cn, prev[cn] });
		cn = prev[cn];
	}
	return { dist[n], path };
}

 

첫번째 다익스트라, 최단 거리와 그 경로를 구한다.

 

2. s_dijkstra

int s_dijkstra(int xn1, int xn2) {
	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 cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;
		if (cn == n) return dist[cn];

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;
			if (cn == xn1 && nn == xn2) continue;
			if (cn == xn2 && nn == xn1) continue;

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

 

두번째 다익스트라, 특정 간선을 제거했을때의 최단 거리를 구한다.

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 edges배열을 초기화한다.
2. 변수 res에 f_dijkstra함수를 수행하고, 최단 거리와 그 경로를 저장한다.
3. 변수 mx를 -1로 초기화하고, 최단 거리의 경로를 for문으로 순회한다.
4. 변수 d에 s_dijkstra함수에 간선이 잇는 두 노드 번호를 매개변수로 전달하여 호출한 후 리턴값을 저장한다.
5. d가 -1일 경우 지연을 최대로 할 수 있는 케이스를 발견했으므로 -1을 출력하고 조기 종료한다.
6. mx가 d보다 작을 경우 mx를 d로 변경한다.
7. 모든 탐색을 마친 후 mx에서 res.first값을 뺀 값을 출력해 최대 지연 시간을 출력한다.

 

트러블 슈팅

1. priority_queue의 operator<함수에서 부등호의 방향을 반대로하여 최대힙을 구현해버렸다.
2. 최대힙을 구현했는데 조기 종료 가지치기를 적용하여 WA를 받았다.
3. priority_queue의 operator<함수 부등호 방향을 정상적으로 변경하여 AC를 받았다.

 

참고 사항

1. 처음에 1에서 n으로 가는 최단 경로의 값과 실제 경로를 구한다.
2. 실제 경로에서 간선을 하나씩 지워가며 최단 경로의 최대값을 구해주면된다.
3. 만약 n에 도달할 수 없는 케이스가 발견된 경우 조기 종료 처리하면 된다.

 

정답 코드

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

const int N = 1001;
int n, m;
struct Edge {
	int nn, nv;
};
vector<Edge> edges[N];
struct Pos {
	int cn, cv;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

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

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

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

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

	vector<pair<int, int>> path;
	int cn = n;
	while (cn != 1) {
		path.push_back({ cn, prev[cn] });
		cn = prev[cn];
	}
	return { dist[n], path };
}

int s_dijkstra(int xn1, int xn2) {
	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 cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;
		if (cn == n) return dist[cn];

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;
			if (cn == xn1 && nn == xn2) continue;
			if (cn == xn2 && nn == xn1) continue;

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

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

	cin >> n >> m;
	while (m--) {
		int a, b, t; cin >> a >> b >> t;
		edges[a].push_back({ b, t });
		edges[b].push_back({ a, t });
	}

	auto res = f_dijkstra();
	int mx = -1;
	for (const auto& data : res.second) {
		int d = s_dijkstra(data.first, data.second);
		if (d == -1) {
			cout << -1;
			return 0;
		}
		if (mx < d) mx = d;
	}
	cout << mx - res.first;
}