[G4] 백준 1277번 발전소 설치 C++ 다익스트라, 최단 경로

리뷰

 

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

노드간 간선을 직접 초기화 하고, 가중치가 소수타입인 다익스트라 문제

 

 

전역 변수

• n : 발전소의 개수
• w : 남아있는 전선의 개수
• m : 전선(간선)의 제한 길이
• Pos : 각 노드의 x, y 좌표 위치를 저장할 구조체
• Edge : 각 간선이 가르키는 다음 노드와 가중치를 정의할 구조체
• Node : 최단 경로를 찾을 때 사용할 구조체
• poses : 각 노드의 위치 정보를 저장할 Pos타입 배열
• lst : 각 노드에서의 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열

 

함수

1. dijkstra

int dijkstra()

 

n번째 발전소 까지 최단 경로를 구하기 위한 함수

1. Node타입 우선순위 큐 pq를 초기화 한다.
2. pq에 1번 발전소와 현재 까지의 거리 0을 추가해 준다.
3. 소수 타입의 벡터 dist를 n + 1크기로 값을 매우 큰 값으로 초기화 해준다.
4. 1번 발전소의 dist값을 0으로 초기화 해준다.
5. pq가 빌 때 까지 반복문을 수행해 준다.
6. 매번 pq에서 요소를 꺼내 Node타입의 변수 node로 초기화 해준다.
7. 변수 node의 값을 현재 노드를 가르키는 cn과 현재 까지의 거리 d로 초기화 해준다.
8. cn의 인접리스트를 순회하며 다음 노드 nn과 간선의 가중치 v를 초기화 해준다.
9. d + v의 값이 nn까지의 최단 경로보다 짧다면 갱신 후 pq에 추가해 준다.
10. 모든 탐색을 마친 후 dist[n]의 1000배를 한 값을 리턴해 준다.

 

문제풀이

1. n, w, m값을 입력 받고, n개의 발전소의 위치 정보를 입력 받아 poses배열에 초기화 해준다.
2. w개의 남아있는 전선 정보를 입력 받아 가중치가 0인 양방향 인접 리스트를 lst에 초기화 해준다.
3. 브루트포스 알고리즘을 통해 각 노드간의 간선 정보를 초기화 해준다. (거리가 m보다 작을 시에만)
4. dijkstra 함수를 통해 1번 발전기에서 n번 발전기 까지의 최단 거리 * 1000값을 구해준 후 출력해 준다.

 

참고 사항

• dijkstra함수의 리턴 값이 int이므로 소수는 자동으로 버림 처리가 된다.
• 좌표 평면상 두 점의 거리는 ((x2 - x1)^2 + (y2 - y1)^2)^1/2이다.

 

정답 코드

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

int n, w;
double m;
struct Pos {
	int x, y;
};
struct Edge {
	int nn;
	double v;
	bool operator<(const Edge& other) const {
		return v > other.v;
	}
};
struct Node {
	int node;
	double d;
	bool operator<(const Node& other) const {
		return d > other.d;
	}
};
Pos poses[1001];
vector<Edge> lst[1001];

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

	while (!pq.empty()) {
		Node node = pq.top(); pq.pop();
		int cn = node.node;
		double d = node.d;
		for (const Edge& edge : lst[cn]) {
			int nn = edge.nn;
			double v = edge.v;
			if (dist[nn] > d + v) {
				dist[nn] = d + v;
				pq.push({ nn, dist[nn] });
			}
		}
	}
	return dist[n] * 1000;
}

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

	cin >> n >> w >> m;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		poses[i] = { x, y };
	}

	while (w--) {
		int a, b; cin >> a >> b;
		lst[a].push_back({ b, 0 });
		lst[b].push_back({ a, 0 });
	}

	for (int i = 1; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			const Pos& cn = poses[i];
			const Pos& nn = poses[j];
			double dist = pow(pow(abs(cn.x - nn.x), 2) + pow(abs(cn.y - nn.y), 2), 0.5);
			if (dist > m) continue;
			lst[i].push_back({ j, dist });
			lst[j].push_back({ i, dist });
		}
	}

	cout << dijkstra();
}