👨‍💻 문제

---

✍️ 풀이 1 - 플로이드 워셜

그냥 문제를 보자마자 생각난 방법이다.

그냥 모든 정점에서 모든 정점으로 가는 최단거리를 구하는 것이다.
플로이드 워셜 알고리즘을 알고 있다면 가장 쉽고 간단한 풀이이다.

하지만 해당 문제에서 요구하는 것은
한 정점을 왕복하는 거리들을 구하는 것이다.

플로이드 워셜은 불필요한 거리들을 구하는 데에 시간을 많이 소모하게 된다.

만약 정점의 수가 훨씬 더 많았다면, 해당 풀이는 시간 초과를 받았을 것이다.

---

✍️ 풀이 2 - 다익스트라

그렇다면 필요한 거리들만 계산하자.

해당 문제는 단방향 그래프로 구성되어 있다.

그렇기에 왕복을 간단히 생각하면,
갈 때는 단방향 그대로 가고,
올 때는 단방향의 역방향으로 가면 된다.

그렇다면 단순히 정방향 그래프과 역방향 그래프를 만든 후,
두 그래프에 모두 다익스트라 알고리즘을 적용시킨다.

    private static ArrayList<Node>[] straightNodes;
    private static int[] straightDistances;

    private static ArrayList<Node>[] reversedNodes;
    private static int[] reversedDistances;
    
	public static void main(String[] args) throws IOException {
        init();

        dijkstra(straightNodes, straightDistances);
        dijkstra(reversedNodes, reversedDistances);
    
    	...
	}

이후 결과 배열을 순회하며, 왕복 거리값의 최대값을 출력한다.

        int maxDist = 0;
        for (int i=0; i<E; i++) {
            maxDist = Math.max(maxDist, straightDistances[i] + reversedDistances[i]);
        }
        System.out.println(maxDist);

시간이 확연히 줄어든 것을 확인할 수 있다.

---

📄 전체 소스코드 - 플로이드 워셜

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

public class _1238 {

    private static final long INF = Long.MAX_VALUE;
    private static int E, V;

    private static int partyPoint;
    private static long[][] dists;

    public static void main(String[] args) throws IOException {
        init();
        floydWarshall();
        System.out.println(getMaxDistToGoPartyAndComeBack());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        E = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        partyPoint = Integer.parseInt(st.nextToken()) - 1;

        dists = new long[E][E];
        for (int i=0; i<E; i++) {
            Arrays.fill(dists[i], INF);
        }

        for (int i=0; i<V; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            long dist = Integer.parseInt(st.nextToken());
            dists[from][to] = dist;
        }
    }

    private static void floydWarshall() {
        for (int across = 0; across < E; across++) {
            for (int from = 0; from < E; from++) {
                if (from == across || dists[from][across] == INF) {
                    continue;
                }
                for (int to = 0; to < E; to++) {
                    if (to == across || to == from || dists[across][to] == INF) {
                        continue;
                    }
                    dists[from][to] = Math.min(dists[from][to], dists[from][across] + dists[across][to]);
                }
            }
        }
    }

    private static long getMaxDistToGoPartyAndComeBack() {
        long result = 0;
        for (int i=0; i<E; i++) {
            result = Math.max(result, dists[i][partyPoint] + dists[partyPoint][i]);
        }
        return result;
    }
}

---

📄 전체 소스코드 - 다익스트라

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 _1238_2 {

    private static int E, V;
    private static int startPoint;

    private static ArrayList<Node>[] straightNodes;
    private static int[] straightDistances;

    private static ArrayList<Node>[] reversedNodes;
    private static int[] reversedDistances;

    private static class Node implements Comparable<Node>{
        int idx;
        int cost;

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

        public int compareTo(Node node) {
            return this.cost - node.cost;
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        dijkstra(straightNodes, straightDistances);
        dijkstra(reversedNodes, reversedDistances);

        int maxDist = 0;
        for (int i=0; i<E; i++) {
            maxDist = Math.max(maxDist, straightDistances[i] + reversedDistances[i]);
        }
        System.out.println(maxDist);

    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        E = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        startPoint = Integer.parseInt(st.nextToken()) - 1;

        straightNodes = new ArrayList[E];
        straightDistances = new int[E];

        reversedNodes = new ArrayList[E];
        reversedDistances = new int[E];

        for (int i=0; i<E; i++) {
            straightNodes[i] = new ArrayList<>();
            reversedNodes[i] = new ArrayList<>();
        }

        for (int i=0; i<V; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            int dist = Integer.parseInt(st.nextToken());

            Node node = new Node(to, dist);
            straightNodes[from].add(node);

            Node reversedNode = new Node(from, dist);
            reversedNodes[to].add(reversedNode);
        }
    }

    private static void dijkstra(ArrayList<Node>[] nodes, int[] dists) {
        for (int i=0; i<E; i++) {
            dists[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(startPoint, 0));

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

            if (node.cost >= dists[node.idx]) {
                continue;
            }
            dists[node.idx] = node.cost;

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