[백준] 골4 - 서강그라운드

14938번: 서강그라운드

문제설명

그래프 문제이다.

지역(노드)이 n개 있고, 각 노드마다 value가 있다. 양방향 그래프로 weight가 있다.

수색할 수 있는 최대 weight가 존재할 때, 얼마나 노드의 value를 최대로 탐색할 수 있는지 묻는 문제이다.

풀이

플로이드-와샬 알고리즘으로 모든 점 최단경로를 구한다. 최대 사이즈가 100이므로 3승을 해도 1초인 1억회 연산을 수행하지 않는다. 그러므로 사용해도 되는 알고리즘이다.

그 후 1번 노드부터 n번 노드까지 모든 노드의 최단경로를 탐색해서 수색 비용보다 작다면 value를 모두 합해서 vector에 삽입한다.

그 후 vector의 최대값을 정답으로 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, r;
int cost[101][101];
int item[101];

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

	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
			cost[i][j] = INT_MAX;

	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++)
	{
		cin >> item[i];
	}

	for (int i = 1; i <= r; i++)
	{
		int a, b, l;
		cin >> a >> b >> l;
		cost[a][b] = min(cost[a][b], l);
		cost[b][a] = min(cost[b][a], l);
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (cost[i][k] == INT_MAX || cost[k][j] == INT_MAX)
					continue;

				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cost[i][i] = 0;
	}

	vector<int> v;
	for (int i = 1; i <= n; i++)
	{
		int sum = 0;
		for (int j = 1; j <= n; j++)
		{
			if (cost[i][j] <= m)
				sum += item[j];
		}
		v.push_back(sum);
	}

	sort(v.begin(), v.end(), greater<int>());

	cout << v[0];

	return 0;
}

소감

플로이드-와샬 알고리즘의 틀을 이해하자

for (k : 1 ~ n)
	for (i : 1 ~ n)
		for (j : 1 ~ n)
			if (cost[i][k] == INT_MAX || cost[k][j] == INT_MAX)
				continue;
			if (cost[i][j] > cost[i][k] + cost[k][j])
				cost[i][j] = cost[i][k] + cost[k][j]

참조