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

접근

이 문제는 다익스트라로 풀 수도, 플로이드 워샬로 풀 수도 있는 문제다. 나는 플로이드로 풀었다. 플로이드 알고리즘의 경우 O(N^3)로 상당히 비효율적인 시간복잡도를 가지긴 하지만, 여기서는 N의 최댓값이 100이기 때문에 제한 시간 안에 가능하다. 또한, 문제를 읽어보면 결국 모든 노드 -> 모든 노드로 가는 최단거리를 구해야하는 문제이기 때문에 다익스트라를 선택해도 결국 N번만큼 함수를 호출해야 한다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ14938 {
    static int INF = 1501;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        int[][] graph = new int[n+1][n+1];
        int[] items = new int[n+1];

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

            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }

        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 l = Integer.parseInt(st.nextToken());

            graph[a][b] = graph[b][a] = l;
        }

        // 플로이드 워샬
        int[][] dist = floyd(graph, n);

        // 최대 아이템 개수 계산
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int sum = 0;

            for (int j = 1; j <= n; j++) {
                if(dist[i][j] <= m)
                    sum += items[j];
            }

            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }

    private static int[][] floyd(int[][] graph, int n) {
        int[][] dist = graph.clone();

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(i == k || k == j || i == j || dist[i][k] == INF || graph[k][j] == INF)
                        continue;

                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + graph[k][j]);
                }
            }
        }

        return dist;
    }
}