[BOJ] 단계별로 풀어보기 - 최단 경로

 

 

 

 

 

https://www.acmicpc.net/step/26

최단 경로 단계

---

코딩 구현 속도와 베이스를 다지기 위해 백준 단계를 하나씩 다 풀어보는 중 ...

 

1. 1753 최단경로: https://www.acmicpc.net/problem/1753

Dijkstra

 

 

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <queue>
	#include <cstring>
	using namespace std;
	typedef pair<int, int> pii;
	int V, E, K, u, v, w;
	int chk[20001];
	vector<pii> adj[20001];
	priority_queue<pii, vector<pii>> pq;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> V >> E >> K;
	for (int i = 0; i < E; ++i){
	cin >> u >> v >> w;
	adj[u].push_back({w, v});
	}
	for (int i = 1; i <= V; ++i) chk[i] = -987654321;
	pq.push({0, K});
	chk[K] = 0;
	while (!pq.empty()){
	pii h = pq.top();
	pq.pop();
	if(chk[h.second] > h.first) continue;
	for (auto &i : adj[h.second]){
	int d = h.first - i.first;
	if (chk[i.second] < d){
	pq.push({d, i.second});
	chk[i.second] = d;
	}
	}
	}
	for (int i = 1; i <= V; ++i){
	if (chk[i] == -987654321) cout << "INF\n";
	else cout << -chk[i] << "\n";
	}
	}

view raw BOJ_1753.cpp hosted with ❤ by GitHub

 

 

 

2. 1504 특정한 최단 경로: https://www.acmicpc.net/problem/1504

주어진 두 정점을 반드시 거쳐야한다 (제약조건) + Dijkstra

 

Dist(u, v) = u ~ v까지 최단 거리 라고 하면,

$Dist(1, v_1)+Dist(v_1,v_2)+Dist(v_2,N)$ 또는,

$Dist(1, v_2)+Dist(v_2,v_1)+Dist(v_1,N)$ 이 답이 된다는 사실을 관찰할 수 있다.

 

따라서 $v_1$과 $v_2$를 시작점으로 하여 Dijkstra를 총 2번 돌려야 한다.

위 수식을 약간 변경하여,

$Dist(v_1, 1)+Dist(v_1,v_2)+Dist(v_2,N)$ 

$Dist(v_2, 2)+Dist(v_2,v_1)+Dist(v_1,N)$

이렇게 얻은 결과값을 계산하여 최솟값을 답으로 하면 AC.

 

	#include <iostream>
	#include <algorithm>
	#include <queue>
	#include <vector>
	using namespace std;
	#define INF 123456789
	typedef pair<int, int> pii;
	int N, E, a, b, c, dis[801], r[2];
	vector<pii> adj[801];
	priority_queue<pii> pq;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> E;
	for (int i = 1; i <= N; ++i) dis[i] = -INF;
	for (int i = 0; i < E; ++i){
	cin >> a >> b >> c;
	adj[a].push_back({c, b});
	adj[b].push_back({c, a});
	}
	cin >> a >> b;
	dis[a] = 0;
	pq.push({0, a});
	while (!pq.empty()){
	pii h = pq.top();
	pq.pop();
	for (auto &i : adj[h.second]){
	int d = h.first - i.first;
	if (dis[i.second] < d){
	dis[i.second] = d;
	pq.push({d, i.second});
	}
	}
	}
	r[0] -= dis[b] + dis[1];
	r[1] -= dis[N] + dis[b];
	for (int i = 1; i <= N; ++i) dis[i] = -INF;
	dis[b] = 0;
	pq.push({0, b});
	while (!pq.empty()){
	pii h = pq.top();
	pq.pop();
	for (auto &i : adj[h.second]){
	int d = h.first - i.first;
	if (dis[i.second] < d){
	dis[i.second] = d;
	pq.push({d, i.second});
	}
	}
	}
	r[0] -= dis[N];
	r[1] -= dis[1];
	r[0] = r[0] < INF ? r[0] : INF;
	r[1] = r[1] < INF ? r[1] : INF;
	r[0] = min(r[0], r[1]);
	if (r[0] == INF) cout << "-1";
	else cout << r[0];
	return 0;
	}

view raw BOJ_1504.cpp hosted with ❤ by GitHub

 

 

3. 9370 미확인 도착지: https://www.acmicpc.net/problem/9370

특정 선분을 반드시 거쳐야한다 (제약조건) + Dijkstra

 

위에 문제가 특정한 정점을 지나는 Dijkstra를 구현하는 문제였다면, 

이 문제는 특정 선분을 지나는 Dijkstra를 구현하는 문제이다.

 

Dijkstra에서 최단 경로를 구할 때,

g-h 선분을 지나는 최단경로들은 따로 chk배열을 이용하여 구분해줌으로써 문제를 해결하였다.

방법은 아래와 같다.

 

1. 최단경로가 갱신될 때, cur와 next가 주어진 선분의 양 끝점이라면, next 정점을 check 해준다.

if ((cur == g && next == h) || (cur == h && next == g)) chk[next] = true; 

여기서 주의할 점은 next 정점의 check 배열만 갱신해준다는 것이다. 

cur도 check 배열을 갱신해주면, cur->next 선분을 지나지 않고 cur만 지나는 정점들도 갱신되어 오답이 발생한다.

 

2. 최단경로가 갱신될 때, cur가 chek 되어있으면, next 정점을 check 해준다.

if (chk[cur] == ture && cur.first + next.first == cost[next]) chk[next] = true;

.first 는 간선의 가중치에 해당하는 부분이고 cost 배열은 각 정점까지의 최단거리가 저장된다.

cur 정점까지 가는 최단경로가 g-h 선분을 지난다고 하면,

cur->next 선분을 통해 next까지 가는 최단경로도 당연히 g-h 선분을 지난다는 걸 알 수 있다.

 

이 문제에서 크게 주의해야할 상황은 두가지가 있다.

1. 동일한 최단경로가 여러개이고, 이 중 g-h를 지나는 경로가 존재할 시

 보통 dijkstra에서 최단 경로를 갱신할 때,

if (cur.first + next.first >= cost[next]) continue;

이런 식으로 거리가 갱신되지 않으면 추가작업(ex. queue push)들을 무시해버린다.

만약 이렇게 코드를 작성하면, 1->3까지 가는 최단 경로가 1->2->3 이렇게 갱신되기 때문에,

1->4 간선이 무시되어 잘못된 해답을 낼 수 있다.

 

2. 최단 경로인 줄 알았던 경로가 마지막에 최단 경로가 아니라고 판별날 시

작성자는 이 부분에서 오답을 뱉어냈었다..

새로 갱신되는 최단 경로가 g-h를 지나지 않을 때 chk 배열을 false로 바꿔주는 코드를 넣지 않아 오답이 발생했었다.

위의 경우에는 1->2->3->4 처음에 이렇게 dijkstra가 돌면서 chk[4] = true 로 갱신된다.

하지만 후에 1->5->4 경로를 지날 때, 이 경로가 최단경로로 갱신되면서 chk[4] = false로 바꿔줘야한다.

 

첨부한 코드는 priority_queue 라이브러리를 간편하게 이용하기 위해 가중치를 모두 음수로 바꿔주어 부등호 방향이 반대로 바뀐다.

	#include <iostream>
	#include <queue>
	#include <vector>
	#include <algorithm>
	using namespace std;
	typedef pair<int, int> pii;
	int T, n, m, t, s, g, h, a, b, d, tmp, cost[2001];
	vector<pii> adj[2001];
	bool chk[2001];
	priority_queue<pii> pq;
	priority_queue<int, vector<int>, greater<int>> destiny;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--){
	cin >> n >> m >> t;
	cin >> s >> g >> h;
	for (int i = 1; i <= n; ++i){
	cost[i] = -0x7fffffff;
	chk[i] = 0;
	adj[i].clear();
	}
	for (int i = 0; i < m; ++i){
	cin >> a >> b >> d;
	adj[a].push_back({-d, b});
	adj[b].push_back({-d, a});
	}
	for (int i = 0; i < t; ++i){
	cin >> tmp;
	destiny.push(tmp);
	}
	pq.push({0, s});
	while (!pq.empty()){
	pii head = pq.top();
	pq.pop();
	for (auto &i : adj[head.second]){
	int dist = head.first + i.first;
	if (dist < cost[i.second]) continue;
	if (dist > cost[i.second]){
	chk[i.second] = 0; // fail point
	cost[i.second] = dist;
	pq.push({dist, i.second});
	}
	if (chk[head.second] && dist == cost[i.second]) chk[i.second] = 1;
	if ((i.second == g && head.second == h) || (i.second == h && head.second == g)) chk[i.second] = 1;
	}
	}
	for (int i = 1; i <= n, !destiny.empty(); ++i)
	{
	if (destiny.top() == i){
	if (chk[i]) cout << i << " ";
	destiny.pop();
	}
	}
	cout << "\n";
	}
	return 0;
	}

view raw BOJ_9370.cpp hosted with ❤ by GitHub

 

 

4. 11657 타임머신: https://www.acmicpc.net/problem/11657

음수인 가중치도 들어오기 때문에 벨만-포드 알고리즘을 이용

 

	#include <iostream>
	#include <algorithm>
	#include <utility>
	#include <vector>
	#define INF 0x7fffffff
	using namespace std;
	typedef pair<int, int> pii;
	int N, M, a, b, c;
	long long dist[501];
	vector<pii> adj[501];
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; ++i){
	cin >> a >> b >> c;
	adj[a].push_back({c, b});
	}
	for (int i = 1; i <= N; ++i) dist[i] = INF;
	dist[1] = 0;
	for (int k = 1; k <= N; ++k){
	for (int i = 1; i <= N; ++i){
	if (dist[i] == INF) continue;
	for (auto &j : adj[i]){
	if (dist[j.second] > dist[i] + j.first){
	dist[j.second] = dist[i] + j.first;
	if (k == N){
	cout << "-1";
	return 0;
	}
	}
	}
	}
	}
	for (int i = 2; i <= N; ++i){
	if (dist[i] == INF) cout << "-1\n";
	else cout << dist[i] << "\n";
	}
	return 0;
	}

view raw BOJ_11657.cpp hosted with ❤ by GitHub

 

 

5. 11404 플로이드: https://www.acmicpc.net/problem/11404

각 정점 사이의 최단거리를 모두 구하는 문제

n 제한이 작기 때문에 플로이드-와샬 알고리즘을 이용

 

	#include <iostream>
	#include <vector>
	#define INF 987654321
	using namespace std;
	int dist[101][101], n, m, a, b, c;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i){
	for (int j = 1; j <= n; ++j){
	if (i != j) dist[i][j] = INF;
	}
	}
	for (int i = 0; i < m; ++i){
	cin >> a >> b >> c;
	dist[a][b] = min(dist[a][b], c);
	}
	for (int k = 1; k <= n; ++k){
	for (int i = 1; i <= n; ++i){
	for (int j = 1; j <= n; ++j){
	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
	}
	}
	for (int i = 1; i <= n; ++i){
	for (int j = 1; j <= n; ++j){
	if (dist[i][j] == INF) cout << "0 ";
	else cout << dist[i][j] << " ";
	}
	cout << "\n";
	}
	return 0;
	}

view raw BOJ_11404.cpp hosted with ❤ by GitHub

 

 

6. 10217 KCM Travel: https://www.acmicpc.net/problem/10217

최단경로보다는 DP가 핵심인 문제 (굳이 Dijkstra를 쓰지 않아도 된다)

 

D[u][m]: 1~u까지 m 이하의 비용을 사용할 때의 최소 소요시간

이렇게 DP table를 정의 내리고 구하면 된다.

 

기존 Dijkstra에서 최단거리를 갱신하는 배열은 보통 cost[] 이렇게 1차원 배열로, 각 정점까지의 최단거리가 저장되었다.

이 문제에선 이 cost 배열을 2차원으로 늘려서 D[u][m] 이렇게 바꾸면 된다.

앞에서 굳이 Dijkstra를 쓰지 않아도 된다고 한 이유는 m 이하의 비용을 맞추는 경로가 최악의 경로일 시 어차피 모든 경로를 다 돌아봐야 하기 때문이다.

따라서 작성자는 우선순위 큐가 아닌, 큐를 이용하여 코드를 작성하였다.

 

시간제한은 10초로 넉넉하기 때문에 컷팅을 빡세게 하지 않아도 통과할 수 있는 문제다.

굳이 실행시간을 줄이겠다면, 

for (int j = newCost; j <= M; ++j){
	if (dist[i.p][j] > newDist) dist[i.p][j] = newDist;
	else break;
}

이런식으로 컷팅을 해줄 수 있다.

만약 m만큼의 비용을 이용하여 구한 최소 소요시간이 

m+1, m+2, m+3, ... 이렇게 기존에 구했던 그 이상의 비용을 사용했을 때마다 적게 걸릴 시

이를 모두 한꺼번에 갱신해준다.

그리고 큐에서 하나씩 값을 꺼내올 때, 위에 해당하는 것들은 걸러주면 실행시간을 줄일 수 있다.

 

	#include <iostream>
	#include <algorithm>
	#include <utility>
	#include <vector>
	#include <queue>
	#define INF 0x7fffffff
	using namespace std;
	struct Ticket{
	int d, c, p;
	};
	int T, N, M, K, u, v, c, d, dist[101][10001], ans;
	vector<Ticket> adj[101];
	queue<Ticket> q;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--){
	cin >> N >> M >> K;
	for (int i = 0; i < K; ++i){
	cin >> u >> v >> c >> d;
	adj[u].push_back({d, c, v});
	}
	for (int i = 1; i <= N; ++i){
	for (int j = 0; j <= M; ++j){
	dist[i][j] = INF;
	}
	}
	dist[1][0] = 0;
	q.push({0, 0, 1});
	while (!q.empty()){
	Ticket h = q.front();
	q.pop();
	if (h.d > dist[h.p][h.c]) continue;
	for (auto &i : adj[h.p]){
	int newCost = h.c + i.c;
	if (newCost > M) continue;
	int newDist = h.d + i.d;
	if (newDist >= dist[i.p][newCost]) continue;
	for (int j = newCost; j <= M; ++j){
	if (dist[i.p][j] > newDist) dist[i.p][j] = newDist;
	else break;
	}
	q.push({newDist, newCost, i.p});
	}
	}
	ans = dist[N][M];
	if (ans != INF) cout << ans << "\n";
	else cout << "Poor KCM\n";
	for (int i = 1; i <= N; ++i) adj[i].clear();
	}
	return 0;
	}

view raw BOJ_10217.cpp hosted with ❤ by GitHub

 

 

7. 1956 운동: https://www.acmicpc.net/problem/1956

1 -> a -> b -> c -> ... -> 1 이렇게 cycle을 이루는 경로 중에서 최단경로를 구하는 문제

V 제한이 400으로 매우 작기 때문에 플로이드-와샬 알고리즘 이용.

 

$ans = Min_{a,b \in V, a\neq b}(Dist[a][b]+Dist[b][a])$

 

	#include <iostream>
	#include <algorithm>
	#define INF 987654321
	using namespace std;
	int V, E, a, b, c, dist[401][401], ans;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> V >> E;
	for (int i = 1; i <= V; ++i){
	for (int j = 1; j <= V; ++j){
	if (i != j) dist[i][j] = INF;
	}
	}
	for (int i = 0; i < E; ++i){
	cin >> a >> b >> c;
	dist[a][b] = c;
	}
	for (int k = 1; k <= V; ++k){
	for (int i = 1; i <= V; ++i){
	for (int j = 1; j <= V; ++j){
	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
	}
	}
	ans = INF;
	for (int i = 1; i <= V; ++i){
	for (int j = 1; j <= V; ++j){
	if (i == j) continue;
	ans = min(ans, dist[i][j] + dist[j][i]);
	}
	}
	if (ans == INF) cout << -1;
	else cout << ans;
	return 0;
	}

view raw BOJ_1956.cpp hosted with ❤ by GitHub