14938. 서강그라운드

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

14938번: 서강그라운드

 

 

아이디어

각 지역에 낙하했을 때 얻을 수 있는 아이템은 아이템이 있는 지역과 낙하한 지역 간 거리가 수색범위를 벗어나지 않는 경우이다.

 

따라서

1. 모든 지역 간의 최단 경로의 길이를 구하고

2. 임의의 낙하 지역에서 타 지역과의 거리가 수색 범위를 벗어나지 않는 경우에 한해 해당 낙하 지역에서 얻을 수 있는 아이템을 계산하고

3. 이 값들을 비교해 최대값을 얻어내면 된다.

 

입력의 크기가 작아 플로이드-워셜 알고리즘을 적용해도 시간 제한을 넘을 일이 없으므로 플로이드-워셜 알고리즘으로 

'모든 지역 간 최단 경로의 길이'를 구하면 된다.

 

 

풀이코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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][n];
        int INF = 15 * 100;
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
        int[] items = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; 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()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;

            graph[A][B] = graph[B][A] = Integer.parseInt(st.nextToken());
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                if (graph[i][j] <= m) {
                    temp += items[j];
                }
            }
            result = Math.max(result, temp);
        }

        System.out.println(result);
    }
}