👨‍💻 문제

---

✍️ 풀이

🧮 다익스트라

출발점과 도착점이 주어지지 않고,
갈 수 있는대로 최대한 도달한 후,

도달한 정점의 수와 가장 먼 정점의 거리를 출력하는 문제이다.

일단 평범한 다익스트라 알고리즘을 작성하였다.

    private static void dijkstra() {
        costs = new int[E + 1];
        Arrays.fill(costs, INF);
        costs[START] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.cost));
        pq.add(new Node(START, 0));

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

            if (costs[node.idx] < node.cost) {
                continue;
            }

            for (Node connectedNode : nodes[node.idx]) {
                int idx = connectedNode.idx;
                int cost = node.cost + connectedNode.cost;
                if (cost < costs[idx]) {
                    costs[idx] = cost;
                    pq.add(new Node(idx, cost));
                }
            }
        }
    }

🔍 결과값 도출

우리가 필요한 정보는 도달한 정점들의 수와 최대 비용이다.

해당하는 결과를 반환한다.

    private static String getResult() {
        int infectedCnt = 0;
        int maxCost = Integer.MIN_VALUE;

        for (int cost : costs) {
            if (cost != INF) {
                infectedCnt++;
                maxCost = Math.max(maxCost, cost);
            }
        }

        return String.format("%d %d\n", infectedCnt, maxCost);
    }

---

📄 전체 소스코드

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.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

    private static final int INF = Integer.MAX_VALUE;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int E, V, START;

    private static List<Node>[] nodes;

    private static int[] costs;

    private static class Node {

        int idx;
        int cost;

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

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            input();
            dijkstra();
            sb.append(getResult());
        }
        System.out.print(sb);
    }

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        E = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        START = Integer.parseInt(st.nextToken());

        nodes = new List[E + 1];

        for (int i = 1; i <= E; i++) {
            nodes[i] = new ArrayList<>();
        }

        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            nodes[from].add(new Node(to, cost));
        }

    }

    private static void dijkstra() {
        costs = new int[E + 1];
        Arrays.fill(costs, INF);
        costs[START] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.cost));
        pq.add(new Node(START, 0));

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

            if (costs[node.idx] < node.cost) {
                continue;
            }

            for (Node connectedNode : nodes[node.idx]) {
                int idx = connectedNode.idx;
                int cost = node.cost + connectedNode.cost;
                if (cost < costs[idx]) {
                    costs[idx] = cost;
                    pq.add(new Node(idx, cost));
                }
            }
        }
    }

    private static String getResult() {
        int infectedCnt = 0;
        int maxCost = Integer.MIN_VALUE;

        for (int cost : costs) {
            if (cost != INF) {
                infectedCnt++;
                maxCost = Math.max(maxCost, cost);
            }
        }

        return String.format("%d %d\n", infectedCnt, maxCost);
    }

}