[백준] 14938번 - 서강그라운드 (Gold 4)

문제 링크

백준 14938번 - 서강그라운드 (Gold 4)

문제 설명

노드의 개수가 N($\leq$ 100)개인 그래프가 주어져 있다.
그래프의 한 노드에서 출발하면 거리가 m 이하인 노드를 모두 방문할 수 있다.
출발 노드에 따라 방문 가능한 노드에 적힌 수의 합은 바뀌게 된다. 가능한 합의 최댓값을 구하시오.

정답 코드 및 설명

먼저 가능한 모든 출발지 - 도착지 사이의 거리를 플로이드-워셜 알고리즘으로 구하자.
그러면 각 출발지마다 방문 가능한 노드들을 구할 수 있고, 적힌 수들의 합도 구할 수 있다.
모든 출발지에 대해 이 값을 구해서 그 중 최댓값을 출력하면 된다.

전체 시간 복잡도는 플로이드-워셜의 $O(N^3)$과 이후 처리에 필요한 $O(N^2)$을 더한 $O(N^3)$이 된다.

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

public class BOJ14938 {
    static final int INF = 5000;
    int n, m;
    int[] items;
    int[][] graph;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        setItems(new StringTokenizer(br.readLine()));
        setGraph(r, br);
    }

    void setItems(StringTokenizer st) {
        items = new int[n];
        for (int i = 0; i < n; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
    }

    void setGraph(int r, BufferedReader br) throws IOException {
        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                graph[i][j] = INF;
            }
        }
        StringTokenizer st;
        int a, b, length;
        while (r-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken()) - 1;
            b = Integer.parseInt(st.nextToken()) - 1;
            length = Integer.parseInt(st.nextToken());
            if (length < graph[a][b])
                graph[a][b] = graph[b][a] = length;
        }
    }

    int[][] FloydWarshall() {
        int[][] minDist = graph.clone();
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (minDist[i][k] + minDist[k][j] < minDist[i][j])
                        minDist[i][j] = minDist[i][k] + minDist[k][j];
                }
            }
        }
        return minDist;
    }

    int maxItems(int[][] minDist) {
        int maxItems = 0;
        for (int i = 0; i < n; i++) {
            int currItems = 0;
            for (int j = 0; j < n; j++) {
                if (minDist[i][j] <= m)
                    currItems += items[j];
            }
            if (currItems > maxItems)
                maxItems = currItems;
        }
        return maxItems;
    }

    void solution() throws IOException {
        input();
        System.out.println(maxItems(FloydWarshall()));
    }

    public static void main(String[] args) throws IOException {
        new BOJ14938().solution();
    }
}