백준 No.14938 서강그라운드 - JAVA

문제

예으이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역 중 하나의 지역에 낙하산을 타고 낙하하여 , 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

 

각 지역은 일정한 길이 l 의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 이내의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자

5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3

풀이

처음에 어디에 떨어지는지 값을 안 주어 문제를 몇번이고 읽어봤는데 값을 안 주는 거 같아 모든 지역에 떨어졌을 경우를 구해 그 중 최댓값을 구하니 정답이었다.

 

dist 배열을 만들고 해당 dist 인덱스가 노드라고 치고 일단 먼저 최단경로를 각각 구한다. 

그렇게 dist 배열에 최단경로를 구하게 되면 dist 배열을 순회하면서 주어진 수색범위 보다 작은 값 중에 최단경로를 구했던 값들을 더해야 한다. 여기서 더하는 값은 문제에서 주어진 item 값이다. 즉 dist 최단 경로는 수색범위에 필요하고 수색범위를 통과하는 노드들은 각 item개수를 더해주면 된다. 

만약 수색범위가 4이고 떨어진 곳이 2번 노드면 2번 노드 아이템 7, 1번노드 아이템 5, 3번 노드 아이템 8. 5번 노드 아이템 3을 구할 수 있따. 7+5+8+3 => 23이다.

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

public class Main {

    static int dist[];

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();

    static int items[];
    static int N,M,R;
    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());   //길의 개수

        st = new StringTokenizer(br.readLine());

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

        graph.add(new ArrayList<>());
        for (int i = 1; i <= N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < R ; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Node(end,cost));
            graph.get(end).add(new Node(start,cost));
        }

        int sum =0 ;
        int temp = 0;
        for (int k = 1; k <= N ; k++) {
            djas(k);

            for (int i =1;i<N+1;i++){
                int num = dist[i];

                if(num != Integer.MAX_VALUE && num < M){
                    sum += items[i];
                }
            }

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

        System.out.println(temp);
    }

    static void djas(int k){
        Arrays.fill(dist,Integer.MAX_VALUE);
        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        queue.add(new Node(k,0));

        dist[k] = 0;

        while (!queue.isEmpty()){
            Node now = queue.poll();

            for(Node next : graph.get(now.v)){
                if(dist[next.v] > dist[now.v] + next.cost){
                    dist[next.v] = dist[now.v] + next.cost;
                    queue.add(new Node(next.v,dist[next.v]));
                }
            }
        }
    }

    static class Node{

        int v;
        int cost;

        public Node(int v,int cost){
            this.v =v;
            this.cost =cost;
        }
    }
}