[C/C++] 백준 14938번 - 서강그라운드

✏️ 문제 링크

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

14938번: 서강그라운드

 

✏️ 문제 설명

 

✏️ 문제 풀이

플로이드 워셜 알고리즘으로 접근하는 문제입니다. 양방향으로 갈 수 있으니 이를 주의해서 인접 행렬을 구현 후

플로이드 워셜로 최단거리를 구해줍니다. 그런 다음에 아이템의 최대 갯수를 얻어야 합니다.

다시하면 인접 행렬의 크기만큼 반복문을 돌리면서 dist[i][j]값이 max값이 아니고 수색범위보다 작다면 sum에 더하고,

i==j라면 sum에 더해준 뒤 1~n까지의 sum값을 비교해서 가장 큰 값을 출력해줍니다.

 

 

✏️ 문제 코드

#include<iostream>
#include<limits.h>
#include<vector>
using namespace std;

long long dist[101][101];
long length[101];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m,r;
	cin >> n >> m>>r;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else
				dist[i][j] = INT_MAX;
		}
	}

	for (int i = 1; i <= n; i++)
		cin >> length[i];
	
	for (int i = 0; i < r; i++) {
		int start, end, time;
		cin >> start >> end >> time;
		if (dist[start][end] > time)
			dist[start][end] = time;
		if (dist[end][start] > time)
			dist[end][start] = time;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}

	long max = -1;
	for (int i = 1; i <= n; i++) {
		long long sum = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j)
				sum += length[i];
			else if (dist[i][j] != INT_MAX && dist[i][j] <= m)
				sum += length[j];
		}
		if (sum > max)
			max = sum;
	}
	cout << max;
}

 

 

✏️ 더 알아보기

https://pooreumjung.tistory.com/300

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)