[Java] BaekJoon 14938. 서강그라운드 (골드4) (Dijkstra)

문제출처: https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

문제이해

 

목표

그래프 -> 노드 : 지역, 간선 : 길
각 노드에는 얻을 수 있는 아이템 개수가 할당되어 있다. 
예은이의 수색범위(M)이 주어질 때, M이하의 비용으로 갈 수 있는 지역은 다 방문이 가능하다. 
예은이가 얻을 수 있는 최대 아이템 개수를 출력하자.

 

풀이

 

다익스트라를 이용한 기본문제이다. 

모든 노드가 첫 번째 노드가 되어 n번의 다익스트라를 진행한다. 

 

단, 가지치기를 하면서 진행 할 때, 비용이 M이하인 경우에만 진행할 수 있도록하자. 

M 초과인 비용이라면 더이상 탐색을 진행하지 않는다. 

 

한 번의 Dijkstra가 끝이나면, 방문했던 적이 있는 노드의 아이템 개수를 모두 합하여
최대 아이템 개수(answer)와 비교해서 갱신 시켜준다.

 

소스코드

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

import static java.lang.System.in;

public class 서강그라운드 {
    static class Edge {
        int dest;
        int price;

        public Edge(int dest, int price) {
            this.price = price;
            this.dest = dest;
        }

    }

    static final int MAX = 1000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        String[] strArr;
        strArr = br.readLine().split(" ");
        int N = Integer.parseInt(strArr[0]); // 노드 개수
        int M = Integer.parseInt(strArr[1]); // 수색범위
        int E = Integer.parseInt(strArr[2]); // 길의ㅏ개수
        int[] items = new int[N];
        // 아이템
        strArr = br.readLine().split(" ");
        ArrayList<Edge>[] arrayList = new ArrayList[N]; // 인접리스트
        for (int i = 0; i < N; i++) { // 아이탬수
            items[i] = Integer.parseInt(strArr[i]);
            arrayList[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) { // 간선 정보
            strArr = br.readLine().split(" ");
            int start = Integer.parseInt(strArr[0]) - 1;
            int dest = Integer.parseInt(strArr[1]) - 1;
            int price = Integer.parseInt(strArr[2]);
            arrayList[start].add(new Edge(dest, price));
            arrayList[dest].add(new Edge(start, price));
        }


        // 다익스트라 시작
        int[] minDp = new int[N];
        int answer = 0;
        PriorityQueue<Edge> queue = new PriorityQueue<Edge>(Comparator.comparingInt(a -> a.price));
        for (int start = 0; start < N; start++) { // (0 -> 시작노드 (price = 0))
            Arrays.fill(minDp, MAX);
            minDp[start] = 0;
            queue.add(new Edge(start, 0));
            while (!queue.isEmpty()) {
                Edge edge = queue.poll();
                if (minDp[edge.dest] < edge.price) { // 갱신필요 x
                    continue;
                }
                for (Edge nextEdge : arrayList[edge.dest]) {
                    int nextPrice = edge.price + nextEdge.price;
                    if (nextPrice <= M && minDp[nextEdge.dest] > nextPrice) {
                        minDp[nextEdge.dest] = nextPrice;
                        queue.add(new Edge(nextEdge.dest, nextPrice));
                    }
                }
            }
            int sum = 0;
            for (int j = 0; j < N; j++) {
                if (minDp[j] != MAX) {
                    sum += items[j];
                }
            }
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }
}