[백준/Java] 14938 : 서강그라운드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Backjoon_14938_서강그라운드 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int value = Integer.MAX_VALUE / 2;

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        int[][] map = new int[n+1][n+1];
        int[] item = new int[n+1];

        for(int i = 1 ; i <= n ; i++ ){
            Arrays.fill(map[i], value);
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= n ; i++){
            item[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0 ; i < r ; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            map[a][b] = c;
            map[b][a] = c;
        }

        for(int j = 1 ; j <= n ; j++){
            map[j][j] = 0;
        }

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

        int answer = 0;
        for(int j = 1 ; j <= n ; j++){
            int sum = item[j];
            for(int k = 1 ; k <= n ; k++){
                if(j == k) continue;
                if(map[j][k] <= m ) sum += item[k];
            }
            answer = Math.max(answer, sum);
        }
        System.out.println(answer);
    }
}

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

 

이번 알고리즘은 플로이드입니다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구해주는 알고리즘으로 알려져 있습니다.

 

해당문제에서는 하나의 정점에서 다른 정점까지의 최소 거리를 수색 범위 기준으로 우선적으로 필터링을 합니다. 그리고 기준 정점과 필터링된 정점의 아이템 갯수의 합을 구하고, 이를 저장합니다. 모든 정점에서도 갯수의 합을 저장하고 이 중 제일 큰 합을 반환하면 됩니다.