14938번: 서강그라운드
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을
www.acmicpc.net
0. m 이하의 cost로 방문 가능한 노드가 가장 많은 노드 찾기
- 다익스트라를 n번 돌리거나, 플로이드-와샬 진행
1. 편의를 위해, 갈 수 없는 노드는 큰 값(2000)으로 초기화한다
- 최대 거리가 15, 노드가 100개이므로 두 노드의 거리는 15*99=1485가 최대값이다
2. 노드 간 거리 정보를 저장하고, 플로이드-와샬을 진행해 각 노드간 거리를 구한다
3. 각 노드 별 방문 가능한 노드들로부터 획득 아이템 갯수를 종합, 최댓값을 출력한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
int r = pint(st.nextToken());
int[][]map=new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(map[i], 2000);
}
int[] item=new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
item[i]=pint(st.nextToken());
}
for (int i = 0; i < r; i++) {
st = new StringTokenizer(br.readLine());
int n1 = pint(st.nextToken())-1;
int n2 = pint(st.nextToken())-1;
int c = pint(st.nextToken());
map[n1][n2]=c;
map[n2][n1]=c;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if(i==k)continue;
for (int j = 0; j < n; j++) {
if(i==j)continue;
map[i][j]=Math.min(map[i][j],map[i][k]+map[k][j]);
}
}
}
int max_item=0;
for (int i = 0; i < n; i++) {
map[i][i]=0;
int temp=0;
for (int j = 0; j < n; j++) {
if(map[i][j]<=m) {
temp+=item[j];
}
}
max_item=Math.max(temp, max_item);
}
System.out.println(max_item);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 20058 - 마법사 상어와 파이어스톰 (0) | 2021.10.25 |
|---|---|
| [백준] 21610 - 마법사 상어와 비바라기 (0) | 2021.10.25 |
| [백준] 1339 - 단어수학 (0) | 2021.10.10 |
| [백준] 14891 - 톱니바퀴 (0) | 2021.09.27 |
| [백준] 16919 - 봄버맨 2 (0) | 2021.09.25 |
| [백준] 4256 - 트리 (0) | 2021.09.25 |
| [백준] 20056 - 마법사 상어와 파이어볼 (0) | 2021.09.07 |
