BOJ 14938 : 서강그라운드 - https://www.acmicpc.net/problem/14938
각 지역에서 모든 지역까지 갈 수 있는 최소 경로를 모두 구하면 된다. 즉, 모든 정점에서 모든 정점까지의 최소 경로를 구해야 한다.
두 가지 방법이 있다. Dijkstra 알고리즘
을 사용하는 방법과 플로이드워셜(Floyd-Warshall) 알고리즘
을 사용하는 방법.
Dijkstra
를 사용할 경우 : 각 지역(낙하한 지역)마다 Dijkstra 알고리즘을 돌려서 모든 지역까지의 최소 거리를 구한 뒤 수색 범위에서 가능한 아이템의 수를 카운트하여 max값을 print한다.
플로이드워셜
을 사용할 경우 : 인접 행렬을 만들어 플로이드워셜 알고리즘을 돌리면 모든 노드부터 모든 노드까지의 최단거리가 구해진다. 이것 역시 시작점마다 수색 범위에서 가능한 아이템 수를 카운트하여 max값을 print하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static final int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
int r = Integer.parseInt(inputs[2]);
int[][] map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i==j) continue;
map[i][j] = INF;
}
}
int[] item_num = new int[n + 1];
inputs = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
item_num[i + 1] = Integer.parseInt(inputs[i]);
}
for (int i = 0; i < r; i++) {
inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
int w = Integer.parseInt(inputs[2]);
map[a][b] = w; // 양방향
map[b][a] = w;
}
// Floyd-Warshall Algorithm
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
// print result
int result = 0;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt=0;
for (int j = 1; j <= n; j++) {
if(map[i][j]<=m){
cnt += item_num[j];
}
}
result = Math.max(result, cnt);
}
System.out.println(result);
}
}
✔ 알고리즘 분류 - 그래프 이론, 다익스트라, 플로이드–와샬
✔ 난이도 - 🟡 Gold 4
딱히 없음