[백준] 14938번 : 서강그라운드 - 자바[Java]

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

14938번: 서강그라운드

풀이

모든 정점에 대해 모든정점까지의 최단거리를 구해야 하기 때문에 그래프 최단거리 알고리즘을 사용했다.

1 <= N <= 100이기 때문에 시간복잡도가 O(N^3)인 플로이드 알고리즘을 사용할 수 있다.

 

로직

1. 전역변수 n, m, r 값을 입력받고, items[], dist[][] 배열을 할당한 다음, dist 배열을 MAX 값으로 초기화한다. (i == j인 경우 0으로 초기화)

2. 각 구역에 있는 아이템 수를 입력받아 items[] 배열에 저장하고, 그래프 정보를 인접 배열 dist[][]에 저장한다.

3. 플로이드 알고리즘을 사용하여  모든 정점에 대해  모든 정점까지의 최단거리(dist)를 구한다.

4. 각 정점을 시작점으로 했을 때 얻을 수 있는 아이템 수를 구하여 최종적으로 얻을 수 있는 최대 아이템 수를 구한다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 10000;

    static int n, m ,r;
    static int[][] dist;
    static int[] items;

    public static void main(String[] args) 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());
        r = Integer.parseInt(st.nextToken());

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

        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], MAX);
            dist[i][i] = 0;
        }

        // 각 구역에 있는 아이템 수 입력받기
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            items[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());

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

        floyd();

        System.out.println(findMaxItems());
    }

    static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

    // 각 정점을 시작점으로 했을 때 얻을 수 있는 아이템 수를 구하여
    // 최종적으로 얻을 수 있는 최대 아이템 수를 반환함
    static int findMaxItems() {
        int max = 0;
        for (int v = 1; v <= n; v++) {
            int sum = 0;
            for (int j = 1; j <= n; j++) {
                if (dist[v][j] <= m) {
                    sum += items[j];
                }
            }

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

        return max;
    }
}