백준 : 다익스트라 - 파티 - 1238번 (java)

다익스트라가 아직 너무 어려워서 문제 정답을 보고 이해하는 느낌으로 풀었다... 아래 블로그에 설명이 잘 되어있어서 이번에는 이런식으로 풀고 다음에 다시 풀어볼 예정!!

https://velog.io/@lifeisbeautiful/Java-%EB%B0%B1%EC%A4%80-1238%EB%B2%88-%ED%8C%8C%ED%8B%B0-with-%EC%9E%90%EB%B0%94

[Java] 백준 1238번 파티 with 자바

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

public class Party {
    private static final int INF = Integer.MAX_VALUE;
    static List<ArrayList<Node>> list = new ArrayList<>(); // 인접리스트
    static List<ArrayList<Node>> backlist = new ArrayList<>(); // 되돌아오는 인접리스트
    static int N, M, X;

    static class Node implements Comparable<Node>{
        int roadNum;
        int time;

        public Node(int roadNum, int time) {
            this.roadNum = roadNum;
            this.time = time;
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //정점 개수
        M = Integer.parseInt(st.nextToken()); //간선 개수
        X = Integer.parseInt(st.nextToken()); //시작 정점

        list = new ArrayList<>();
        backlist = new ArrayList<>();

        for (int i = 0; i <=N; i++){
            list.add(new ArrayList<>());
            backlist.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken()); // 시작 정점
            int m = Integer.parseInt(st.nextToken()); // 도착 정점
            int t = Integer.parseInt(st.nextToken()); // 가중치

            list.get(n).add(new Node(m, t));
            backlist.get(m).add(new Node(n, t));
        }

        int max = Integer.MIN_VALUE;

        int result[] = dijkstra(list);
        int backResult[] = dijkstra(backlist);

        for (int i = 1; i <=N; i++) // 다익스트라 함수를 사용해서 구한 값으로 가장 오래걸리는 값 구하기
            max = Math.max(max, result[i] + backResult[i]);

        System.out.println(max);
    }
    static int[] dijkstra(List<ArrayList<Node>> list){
        PriorityQueue<Node> que = new PriorityQueue<>();

        boolean visit[] = new boolean[N + 1];
        int dist[] = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[X] = 0;

        que.offer(new Node(X, 0));

        while(!que.isEmpty()){
            Node queNode = que.poll();
            int num = queNode.roadNum;
            if (visit[num])
                continue;
            for (Node node : list.get(num)){
                if( !visit[node.roadNum] && dist[node.roadNum] > (dist[num] + node.time)  ) {
                    dist[node.roadNum] = dist[num] + node.time;
                    que.offer(new Node(node.roadNum, dist[node.roadNum]));
                }
            }
        }
        return dist;
    }

}