파티_1238.md

🍾 [1238] 파티

난이도: 골드 3
소요 시간: 34분
메모리: 16440KB
시간: 156ms

리뷰

• 그래프에 포함된 정점과 그래프에 포함되지 않은 정점 중 최단거리를 구하는 방법을 두가지로 풀어봤다.

전체 코드(완탐 - 164ms)

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

public class Main_1238_파티 {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        List<Node>[] go = new ArrayList[N + 1];
        List<Node>[] back = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            go[i] = new ArrayList<>();
            back[i] = new ArrayList<>();
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            go[start].add(new Node(end, T));
            back[end].add(new Node(start, T));
        }

        int[] arr_go = dijkstra(N, X, go);
        int[] arr_back = dijkstra(N, X, back);

        int answer = arr_go[1] + arr_back[1];
        for (int i = 2; i <= N; i++) {
            answer = Math.max(answer, arr_go[i] + arr_back[i]);
        }
        System.out.println(answer);
    }

    static int[] dijkstra(int N, int X, List<Node>[] list) {
        int[] arr = new int[N + 1];
        Arrays.fill(arr, 987654321);
        arr[X] = 0;

        boolean[] visited = new boolean[N + 1];
        int cnt = 0;

        while (cnt++ < N) {
            int v = 0;
            int e = 987654321;

            for (int i = 1; i <= N; i++) {
                if (!visited[i] && arr[i] < e) {
                    v = i;
                    e = arr[i];
                }
            }
            visited[v] = true;
            for (Node tmp : list[v]) {
                if (visited[tmp.i]) continue;
                int t = e + tmp.t;
                if (t < arr[tmp.i]) {
                    arr[tmp.i] = t;
                }
            }
        }
        return arr;
    }

    static class Node{
        int i, t;

        Node(int i, int t) {
            this.i = i;
            this.t = t;
        }
    }
}

전체 코드(우선순위 큐 - 156ms)

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

public class Main_1238_파티 {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        List<Node>[] go = new ArrayList[N + 1];
        List<Node>[] back = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            go[i] = new ArrayList<>();
            back[i] = new ArrayList<>();
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            go[start].add(new Node(end, T));
            back[end].add(new Node(start, T));
        }

        int[] arr_go = dijkstra(N, X, go);
        int[] arr_back = dijkstra(N, X, back);

        int answer = arr_go[1] + arr_back[1];
        for (int i = 2; i <= N; i++) {
            answer = Math.max(answer, arr_go[i] + arr_back[i]);
        }
        System.out.println(answer);
    }

    static int[] dijkstra(int N, int X, List<Node>[] list) {
        int[] arr = new int[N + 1];
        Arrays.fill(arr, 987654321);
        arr[X] = 0;

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

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            if (arr[node.i] < node.t) {
                continue;
            }

            for (Node tmp : list[node.i]) {
                int t = node.t + tmp.t;
                if (t < arr[tmp.i]) {
                    arr[tmp.i] = t;
                    pq.add(new Node(tmp.i, t));
                }
            }
        }
        return arr;
    }

    static class Node implements Comparable<Node> {
        int i, t;

        Node(int i, int t) {
            this.i = i;
            this.t = t;
        }

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