[백준 C++] 14938 서강그라운드 - 플로이드워셜

14938번: 서강그라운드

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

const int Infinite = INT_MAX;

int N, M, R;
int Item[101];
int Distance[101][101];

void FloydWarshall()
{
	for (int k = 1; k <= N; ++k)
	{
		for (int s = 1; s <= N; ++s)
		{
			for (int e = 1; e <= N; ++e)
			{
				if (s == e || s == k || k == e
					|| Distance[s][k] == Infinite
					|| Distance[k][e] == Infinite)
				{
					continue;
				}

				Distance[s][e] = min(Distance[s][e], Distance[s][k] + Distance[k][e]);
			}
		}
	}
}

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

	cin >> N >> M >> R;
	for (int i = 1; i <= N; ++i)
	{
		cin >> Item[i];
	}
	
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (i == j)
			{
				continue;
			}

			Distance[i][j] = Infinite;
		}
	}

	for (int i = 0; i < R; ++i)
	{
		int S, E, W;
		cin >> S >> E >> W;
		Distance[S][E] = W;
		Distance[E][S] = W;
	}

	FloydWarshall();

	int MaxItem = 0;
	for (int s = 1; s <= N; ++s)
	{
		int Sum = 0;
		for (int e = 1; e <= N; ++e)
		{
			if (Distance[s][e] > M)
			{
				continue;
			}

			Sum += Item[e];
		}

		if (Sum > MaxItem)
		{
			MaxItem = Sum;
		}
	}

	cout << MaxItem;
}

---

 

플로이드-워셜 알고리즘을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 각 노드간의 최단거리 계산 - 플로이드-워셜

2. 1 부터 N 사이의 낙하지점 선택

3. 2번에서 선택한 낙하지점부터 다른 노드까지의 최단거리와 수색범위 비교

4. 수색범위 내에 존재하는 모든 노드의 아이템 개수 카운팅

5. 2~4 반복 후, 카운팅된 각 아이템 개수 중 최대값 출력