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

⭐ 문제링크

---

1. 문제 요약

• 특정 지역에서 낙하 후, 수색 범위 내의 모든 지역에서 아이템을 수집.
• 예은이가 최대 아이템을 수집할 수 있는 경우를 계산.

---

2. 풀이

해당 문제는 수색범위가 중요하다. 그렇기 때문에 핵심 전략은 다익스트라이다.

또한 특정 출발지를 정해주지 않기 때문에, 모든 노드를 출발지로 삼아 최단거리를 계산해야 한다. 그렇다면 전체 풀이는 다음과 같다.

1. 모든 노드를 출발지로 삼아 다익스트라로 최단 거리 계산

• 특정 노드에 대한 다른 노드의 최단거리가 수색범위를 넘는지 확인
• 넘지 않는다면 다른 노드의 아이템을 수집

2. 모든 노드의 아이템 중 가장 큰 값이 정답

---

3. 핵심코드

        int maxItem = 0;
        for (int k = 1; k <= N; k++) {
            findMinRoute(k);
            int sum = 0; // 각 시작 지점마다 초기화
            for (int i = 1; i <= N; i++) {
                if (dijkstra[i] <= M) {
                    sum += items[i];
                }
            }
            maxItem = Math.max(sum, maxItem);
        }

        System.out.println(maxItem);
    }

---

4. 전체코드

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

public class Main {

    static class Node implements Comparable<Node> {
        int to;
        int cost;

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

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    static List<Node>[] graph;
    static int items[];
    static int dijkstra[];
    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];
        dijkstra = new int[N + 1];
        graph = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
            graph[i] = 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[start].add(new Node(end, cost));
            graph[end].add(new Node(start, cost));
        }

        int maxItem = 0;
        for (int k = 1; k <= N; k++) {
            findMinRoute(k);
            int sum = 0; // 각 시작 지점마다 초기화
            for (int i = 1; i <= N; i++) {
                if (dijkstra[i] <= M) {
                    sum += items[i];
                }
            }
            maxItem = Math.max(sum, maxItem);
        }

        System.out.println(maxItem);
    }

    static void findMinRoute(int k) {
        Arrays.fill(dijkstra, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(k, 0));

        dijkstra[k] = 0;

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

            for (Node next : graph[now.to]) {
                if (dijkstra[next.to] > dijkstra[now.to] + next.cost) {
                    dijkstra[next.to] = dijkstra[now.to] + next.cost;
                    pq.add(new Node(next.to, dijkstra[next.to]));
                }
            }
        }
    }
}