백준 14938 c++ "서강그라운드" -[PlusUltraCode]

[필자 사고]

 

문제를 접하고 최단거리 구하는 문제라 생각하였다.

 

처음에는 다익스트라 알고리즘을 사용하여 문제를 풀었다.

 

문제를 푸는 중간에 이 문제는 플로이드-워셜 알고리즘을 사용하면 쉽게 해결할 수 있다는 걸 느꼇다.

 

간단하게 플로이드-워셜 알고리즘을 설명하겠다.

 

시작 ,중간, 끝 이 있을때 

 

D[시작][끝] =D[시작][중간] + D[중간][끝] 이러한 식이 플로이드 워셜이다.

 

시간복잡도는 O(n^3)이므로 N의 수를 확인해보니 100정도라 문제 없었다.

 

다익스트라에만 매몰되지 않고 좀 더 유기적으로 생각해야 할 필요가 있는거 같았다.

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
using namespace std;

typedef pair<int, int> Node;

int N, M, R;

vector<int> item;
vector<vector<Node>> Arr;
vector<bool> visited;
vector<vector<long>> pathLoad;

void Dijkstra(int start) {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,start });
	pathLoad[start][start] = 0;

	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		pq.pop();
		if (visited[nowIdx] == true)continue;
		visited[nowIdx] = true;
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			if (visited[nextIdx] == false &&
				pathLoad[start][nextIdx] > pathLoad[start][nowIdx] + nextCost) {
				pathLoad[start][nextIdx] = pathLoad[start][nowIdx] + nextCost;
				pq.push({ pathLoad[start][nextIdx],nextIdx });
			}
		}
	}
}

void Input() {
	cin >> N >> M >> R;
	item.resize(N + 1);
	visited.resize(N + 1);
	Arr.resize(N + 1);
	pathLoad.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		pathLoad[i].resize(N + 1, INT_MAX);
		
	}
	for (int i = 0; i <= N; i++) {
		pathLoad[i][i] = 0;
	}
	for (int i = 1; i <= N; i++) {
		cin >> item[i];
	}
	for (int i = 0; i < R; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		Arr[e].push_back({ w,s });
	}
}




int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	int itemCount = -1;
	for (int i = 1; i <= N; i++) {
		visited.clear();
		visited.resize(N + 1, false);
		Dijkstra(i);
		int count = 0;
		for (int k = 1; k <= N; k++) {
			if (pathLoad[i][k] <= M) {
				count += item[k];
			}
		}
		if (itemCount < count) {
			itemCount = count;
		}
	}
	cout << itemCount;
}