[BOJ/14938] 서강 그라운드, c++

www.acmicpc.net/problem/14938

14938번: 서강그라운드

한줄 후기 : 앞으로 모든 문제가 n 제한 100이면 좋겠다.

 

 

문제를 짧게 설명하자면 1~n 노드까지 중에 수색범위 m 이내로 다른 노드에 가서 아이템을 주워올 수 있는데 어떤 노드에 내려서 얻을 수 있는 아이템 합 중 최대를 찾으면 되는 문제입니다.

 

//AC
//BOJ 14938 서강그라운드
#include <iostream>
#define INF 987654321
using namespace std;
int item[101];
int road[101][101];
int main(){
	int n, m, r, tmp, sum = 0, ans = 0;
	cin >> n >> m >> r;
	for(int i=1; i<=n; i++){
		scanf("%d", &item[i]);
	}
	for(int i=0; i<r; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		road[a][b] = c;
		road[b][a] = c;
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(road[i][j] == 0){
				road[i][j] = INF;
			}
			if(i==j)	road[i][j] = 0;
		}
	}
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(road[i][k] + road[k][j] < road[i][j]){
					road[i][j] = road[i][k] + road[k][j];
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		sum = 0;
		for(int j=1; j<=n; j++){
			if(road[i][j] <= m){
				sum += item[j];
			}
		}
		ans = max(sum, ans);
	}
	cout << ans;
	return 0;
}

문제를 보시면 n이 100이하로 들어옵니다.

이때 의심해야죠

아 이거 플로이드 와샬 가능하겠다.

 

어차피 수색범위 m이내를 찾으려면 모든 노드간의 최단거리를 구해야합니다.

다익스트라로도 풀릴 것 같지만, 전 n 제한이 작은 것을 보고 플로이드 와샬로 최단거리를 구했습니다.

플로이드 와샬은 거쳐가는 노드 (k) 를 모든 노드로 탐색하면서 start-k-end 거리가 현재 start-end 거리보다 짧으면 갱신시켜주는 방식입니다.

시간복잡도는 3중 for문 이므로 O(n^3)

출제자가 플로이드 와샬을 허용하는 문제는 어지간해서는 거의 n이 100으로 주어집니다.

 

모든 노드 간 최단거리를 구했다면, 모든 노드를 한번씩 돌면서 아이템 합의 최댓값을 찾아 출력해주면 됩니다.

자기 자신 노드의 아이템 값도 더해야하는 걸 잊지 맙시다.