[G4] 백준 14938번 서강그라운드 C++ 다익스트라, 최단 경로

리뷰

 

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

각 지역에서 갈 수 있는 지역을 다익스트라로 구하고, 아이템 개수의 합을 구하는 문제

 

 

전역 변수

• n : 지역의 개수를 저장할 변수
• m : 갈 수 있는 최대 거리를 저장할 변수
• r : 간선의 개수를 저장할 변수
• t : 각 지역의 아이템 개수를 저장할 정수형 배열
• Edge : 간선의 연결된 노드와 가중치를 정의하기 위한 구조체
• edges : 간선을 인접 리스트로 저장하기 위한 Edge타입 벡터 배열
• Cur : 시뮬레이션 시 현재 노드와 현재까지의 거리를 정의할 구조체, 거리를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

void dijkstra(int sn)

 

시작 지역으로 부터 갈 수 있는 모든 지역을 탐색하고 가질 수 있는 아이템 개수를 구하는 함수

1. Cur타입의 우선순위 큐 pq를 초기화 해준다.
2. pq에 초기 지역인 sn과 현재 까지 이동한 거리 0을 push해준다.
3. 정수형 벡터 dist를 n + 1크기로 값은 모두 매우 큰 값으로 설정해 준다.
4. 초기 지역 sn의 dist값을 0으로 초기화 해준다.
5. pq가 빌 때 까지 while루프를 순회하며 각 루프마다 요소를 한개씩 꺼내어 준다.
6. 정수형 변수 cn, d에 현재 탐색중인 지역의 번호와 현재까지의 이동 거리를 파싱해 준다.
7. cn의 인접리스트를 순회하며 정수형 변수 nn에 다음 지역의 번호, nd에 현재 이동 거리 + 간선의 가중치를 더해준다.
8. 만약 nd가 m보다 클 경우 수색 범위를 초과하므로 continue처리를 진행해 준다.
9. 만약 dist의 nn인덱스의 값이 nd보다 크다면 dist[nn]을 nd로 변경해 주고 pq에 nn과 nd를 push해준다.
10. while루프가 도는 동안 갈 수 있는 지역을 모두 찾아준다.
11. 정수형 변수 sum을 0으로 초기화 하고 모든 지역을 순회해 준다.
12. 만약 해당 지역까지의 거리가 dist의 기본값이 아니라면 해당 지역의 아이템 개수만큼 sum에 더해준다.
13. ans를 ans와 sum중 큰 값으로 초기화 해준다.

 

문제풀이

1. n, m, r값을 입력 받고 n개의 지역에 존재하는 아이템 개수를 배열 t에 입력 받아준다.
2. r개의 간선 정보를 입력 받아주고, 배열 edges에 양방향 간선으로 추기해 준다.
3. n개의 지역을 순회하며 각 지역의 번호를 dijkstra함수의 매개변수로 전달하여 함수를 호출해 준다.
4. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• dijkstra 함수 내의 dist는 해당 지역에 갈 수 있는지 여부만 파악하고, 값은 t배열에 저장된 값으로 더해주어야 한다.

 

정답 코드

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

int n, m, r, ans;
int t[101];
struct Edge {
	int nn, w;
};
vector<Edge> edges[101];
struct Cur {
	int cn, d;
	bool operator<(const Cur& other) const {
		return d > other.d;
	}
};

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

	while (!pq.empty()) {
		Cur cur = pq.top(); pq.pop();
		int cn = cur.cn, d = cur.d;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nd = d + edge.w;
			if (nd > m) continue;
			if (dist[nn] > nd) {
				dist[nn] = nd;
				pq.push({ nn, nd });
			}
		}
	}

	int sum = 0;
	for (int i = 1; i <= n; ++i) if (dist[i] != 2e9) sum += t[i];
	ans = max(ans, sum);
}

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

	cin >> n >> m >> r;
	for (int i = 1; i <= n; ++i) cin >> t[i];
	while (r--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}
	for (int i = 1; i <= n; ++i) dijkstra(i);
	cout << ans;
}