[백준][Gold III] Java - 1238번 : 파티

https://www.acmicpc.net/problem/1238

 

□ 문제 : 최단거리 중 가장 큰 값 구하기

• 각 마을(정점)으로 가는 단방향 노드가 주어짐(노드, 거리값)
• 문제에서 요구하는 마을을 갔다 오는 최단거리들 중 가장 큰 값을 반환하는게 문제

□ 사용 알고리즘

• 다익스트라(Dijkstra)

□ 전체 코드

import org.w3c.dom.Node;

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N, M, X;
    static List<Node>[] nomalGraph;
    static List<Node>[] reverseGraph;
    static int[] goDist;
    static int[] comebackDist;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        input();

        dijkstra(X, goDist, reverseGraph);
        dijkstra(X, comebackDist, nomalGraph);

        int answer = 0;
        for(int i = 0; i < N + 1; i++){
            answer = Math.max(goDist[i] + comebackDist[i], answer);
        }

        System.out.println(answer);
    }

    static void input() throws IOException {
        nomalGraph = new ArrayList[N + 1];
        reverseGraph = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            nomalGraph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }

        goDist = new int[N + 1];
        comebackDist = new int[N + 1];
        Arrays.fill(goDist, Integer.MAX_VALUE);
        Arrays.fill(comebackDist, Integer.MAX_VALUE);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            nomalGraph[s].add(new Node(e, d));
            reverseGraph[e].add(new Node(s, d));
        }
    }

    static void dijkstra(int start, int[] arr, List<Node>[] graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dist));
        pq.add(new Node(start, 0));
        arr[start] = 0;

        while (!pq.isEmpty()){
            Node now = pq.poll();
            int nowIndex = now.node;
            int dist = now.dist;
            if(arr[nowIndex] < dist) continue;

            for(int i = 0; i < graph[nowIndex].size(); i++){
                Node next = graph[nowIndex].get(i);
                int nextIndex = next.node;
                int nextDist = next.dist;

                if(arr[nextIndex] > arr[nowIndex] + nextDist){
                    arr[nextIndex] = arr[nowIndex] + nextDist;
                    pq.add(next);
                }
            }
        }
    }

    static class Node {
        private int node;
        private int dist;

        public Node(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

}

 

□ 풀이 과정

1. Node클래스 선언

 static class Node {
        private int node;
        private int dist;

        public Node(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

 

2. 변수 정의

• int[] goDist : 마을로 갈 때의 각 정점별 최단거리
• int[] comebackDist : 원래 위치로 돌아 올 때의 최단거리
• List<Node>[] nomalGraph : 돌아올 때 거리 계산에 필요한 인접리스트
• List<Node>[] reverseGraph : 갈 때 거리 계산에 필요한 인접리스트
  ※ 일반적인 다익스트라는 A에서 각 정점으로 가는 최단 거리를 구할 때 사용된다 그러나 해당 문제는 왕복이므로
  각 정점에서 A로 가는 최단 거리도 구해야한다. 이 때 사용 할 수 있는게 역방향 그래프이다.

3. 입력받기

static void input() throws IOException {
        nomalGraph = new ArrayList[N + 1];
        reverseGraph = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            nomalGraph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }

        goDist = new int[N + 1];
        comebackDist = new int[N + 1];
        Arrays.fill(goDist, Integer.MAX_VALUE);
        Arrays.fill(comebackDist, Integer.MAX_VALUE);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            nomalGraph[s].add(new Node(e, d));
            reverseGraph[e].add(new Node(s, d));
        }
    }

• 각 인접 리스트를 초기화 해준다.
• 최단거리값을 구하기 위해 거리 배열을 Inter.MAX_VALUE로 초기화한다.
• 간선을 입력받는다.

4. 다익스트라 알고리즘 구현

static void dijkstra(int start, int[] arr, List<Node>[] graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dist));
        pq.add(new Node(start, 0));
        arr[start] = 0;

        while (!pq.isEmpty()){
            Node now = pq.poll();
            int nowIndex = now.node;
            int dist = now.dist;
            if(arr[nowIndex] < dist) continue;

            for(int i = 0; i < graph[nowIndex].size(); i++){
                Node next = graph[nowIndex].get(i);
                int nextIndex = next.node;
                int nextDist = next.dist;

                if(arr[nextIndex] > arr[nowIndex] + nextDist){
                    arr[nextIndex] = arr[nowIndex] + nextDist;
                    pq.add(next);
                }
            }
        }
    }

• Node의 dist를 기준 정렬되도록 우선큐를 생성한다.
• 시작 Node를 넣어준다.
• 거리값이 현재 거리보다 크면 넘어간다(갱신 불필요)
• 간선을 순회하여 해당 경로를 지나서 가는 거리값이 원래 값보다 작으면 갱신한다.