[G3] 백준 11562번 백양로 브레이크 C++ 다익스트라, 플로이드 와샬

리뷰

 

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

다익스트라로도 풀이가 가능한데 시간이 아슬아슬하다.

 

 

전역 변수

• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• k : 쿼리의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, n + 1 * n + 1크기의 2차원 벡터 dist를 매우 큰 값으로 초기화 해준다.
2. m개의 간선 정보를 받아 dist벡터에 양방향 간선을 추가해 준다.
3. 이 때 만약 e가 0이면 반대 방향의 가중치는 1로, e가 1이면 양 방향 모두 가중치를 0으로 저장해 준다.
4. 간선 입력을 모두 받은 후엔 자기 자신으로 이동하는 가중치를 모두 0으로 저장해 준다.
5. 플로이드 와샬 알고리즘을 수행하여 각 노드간 최단 거리를 갱신하여 dist벡터에 저장해 준다.
6. k값을 입력 받고, 시작 노드와 이동 노드를 각각 sn, dn에 입력 받아준다.
7. dist[sn][dn]에 저장된 값을 출력하고 줄 바꿈을 수행해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 다익스트라는 간선이 적고 함수 실행 횟수가 적을수록 최단 경로 탐색에 유리하다.
• 플로이드 와샬은 노드가 적을수록 최단 경로 탐색에 유리하다.
• 플로이드 와샬을 통해 최단 거리를 갱신해 놓는다면 초기 과정 이후엔 O(1)로 노드간 최단 거리를 찾을 수 있다.

 

정답 코드

1. 플로이드 와샬 풀이법

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

int n, m, k;

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

	cin >> n >> m;
	vector<vector<int>> dist(n + 1, vector<int>(n + 1, 2e9));
	while (m--) {
		int u, v, e; cin >> u >> v >> e;
		if (!e) {
			dist[u][v] = 0;
			dist[v][u] = 1;
		}
		else {
			dist[u][v] = 0;
			dist[v][u] = 0;
		}
	}
	for (int i = 1; i <= n; ++i) dist[i][i] = 0;

	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (dist[i][k] != 2e9 && dist[k][j] != 2e9) {
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
	}

	cin >> k;
	while (k--) {
		int sn, dn; cin >> sn >> dn;
		cout << dist[sn][dn] << "\n";
	}
}

 

2. 다익스트라 풀이법

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

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

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv;

		if (dist[cn] < cv) continue;
		if (cn == dn) return dist[dn];
		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = edge.nv;
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, cv + nv });
			}
		}
	}
	return -1;
}

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

	cin >> n >> m;
	while (m--) {
		int u, v, e; cin >> u >> v >> e;
		if (!e) {
			edges[u].push_back({ v, 0 });
			edges[v].push_back({ u, 1 });
		}
		else {
			edges[u].push_back({ v, 0 });
			edges[v].push_back({ u, 0 });
		}
	}
	cin >> k;
	while (k--) {
		int sn, dn; cin >> sn >> dn;
		cout << dijkstra(sn, dn) << "\n";
	}
}