14938 서강그라운드

처음에 이 문제를 접근할 때, 어려웠던 점은 양방향 그래프를 표현하는 방법이 헷갈렸다.

map과 2차원 배열 중에 어느 걸로 나타낼 지 고민하다 두 가지 방식을 다 해봤는데, map을 사용했을 때의 문제점은 한 정점과 다른 정점 사이의 최단 경로를 표현하기 애매했다.

그리고 DFS, BFS로 접근하려 했기 때문에 모든 정점들에 대해 탐색을 시도하려 했다. 하지만 그럴 필요 없이 이 문제에 딱 알맞는 알고리즘이 존재했는데, 플로이드 와샬 알고리즘이다.

플로이드 와샬 알고리즘을 사용하는건 다음과 같다.

1. 모든 정점에서 다른 정점들까지 최단 경로를 알고 싶음
2. 음수의 가중치를 갖는 간선에서의 최단 경로르 알고 싶음

단, 제약 조건도 있는데 다음과 같다.

1. 음수 가중치를 갖는 사이클에서는 알고리즘의 정당성을 보장 못함
   • 음의 무한대로 발산할 수 있기 때문에, 음수 사이클이 있는 경우엔 미리 검사해주어야 함

최단 경로를 찾는 알고리즘의 종류 중에 하나인 다익스트라와 비교했을 때, 다익스트라는 O(ElogV)의 시간 복잡도를 갖고, 모든 정점들에 대해 탐색한다면 O(V * ElogV)의 복잡도를 갖는다. 다만 구현이 조금 복잡하다.

반면, 플로이드는 O(V^3)의 복잡도를 갖는데 최단 경로 외에 모든 정점들을 탐색하기 때문이다.

 

이제 문제에 적용해보자. 문제의 요구조건은 탐색할 수 있는 범위 내의 아이템들의 최대 합이다. 다르게 말하면, 모든 정점 쌍들의 최단 경로들을 구한 후에 탐색 범위내의 정점이라면 모두 더한 값이 된다.

 

정답코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_SIZE 101
#define INF 987654321
int N, M, T[MAX_SIZE] = { 0, }, R;
int dist[MAX_SIZE][MAX_SIZE] = { {0,0} };
int ans = 0;
void setting()
{
	for (int i = 1; i < MAX_SIZE; i++) {
		for (int j = 1; j < MAX_SIZE; j++) {
			if(i != j)
				dist[i][j] = INF;
		}
	}
}
void floyd()
{
	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];
				}
			}
		}
	}
}
int main()
{
	cin >> N >> M >> R;
	for (int i = 1; i <= N; i++) {
		cin >> T[i];
	}
	setting();
	for (int i = 0; i < R; i++) {
		int s, e, d;
		cin >> s >> e >> d;
		dist[s][e] = d;
		dist[e][s] = d;
	}
	floyd();
	for (int i = 1; i <= N; i++) {
		int sum = T[i];
		for (int j = 1; j <= N; j++) {
			if (i == j)
				continue;
			if(dist[i][j] <= M)
				sum += T[j];
		}
		ans = max(sum, ans);
	}
	printf("%d\n", ans);
	return 0;
}