백준 1238번 : 파티 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

파티 골드 3

 

📖 문제

 

O(N^3) 인 플로이드 워샬은 사용불가능하고,

다익스트라로 풀어야하는 문제다.

 

그런데 X→모든 정점은 구하겠는데 

모든 정점→X를 편하게 구하는 법을 몰라서 

각 정점에서 다익스트라 알고리즘을 돌려서 X까지의 값을 구하는 식으로 했다. 

 

이 후 다른 사람의 풀이를 봤는데 

정말 놀랍다. 

 

단방향이지만 역방향으로 그래프를 만들어서

// 기존 
X -> All
All -> X

// 다른사람들의 풀이
X -> All 
X <- All

로 X에서 모든정점으로 가는 그래프를 만들고

X로 오는 모든 정점으로 가는 역방향 그래프를 만드는 것이다.

 

좋은 것을 배웠다..

 

 

---

🔅 문제 풀이 [x→ all → x]

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

public class Main {

    static class Node {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
    static List<Node>[] graph;


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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int[] xToAllDiff = new int[n + 1];
        int[] AllToXDiff = new int[n + 1];

        graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();

        }

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

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());

            graph[A].add(new Node(B, T));
        }

        //x -> 모든 정점으로의 최단거리
        Arrays.fill(xToAllDiff, Integer.MAX_VALUE);
        xToAllDiff[x] = 0;
        bfs(x, xToAllDiff);


        // 오고 가는데 가장 오래걸리는 소요시간 구하기
        // 모든 정점 -> x 까지 최단거리
        int max = 0;
        for (int i = 1; i <= n; i++) {
            Arrays.fill(AllToXDiff, Integer.MAX_VALUE);
            AllToXDiff[i] = 0;
            bfs(i, AllToXDiff);

            // i -> x + x -> i 까지 가는데 최단거리의 합중 최댓값을 갱신
            if (AllToXDiff[x] + xToAllDiff[i] > max) {
                max = AllToXDiff[x] + xToAllDiff[i];
            }
        }

        System.out.println(max);
    }

    private static void bfs(int start, int[] diff) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(new Node(start, 0));


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


            List<Node> list = graph[current.idx];
            for (Node node : list) {

                if (diff[node.idx] > node.cost + diff[current.idx]) {
                    diff[node.idx] = node.cost + diff[current.idx];
                    pq.add(new Node(node.idx, diff[node.idx]));
                }
            }

        }
    }
}

 

🔅 문제 풀이 [x→ all, ← all]

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

public class Main {

    static class Node {
        int idx;
        int cost;

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

    static int n;

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

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int[] xToAllDiff = new int[n + 1];
        int[] AllToXDiff = new int[n + 1];
        
        List<Node>[] graph = new List[n + 1];
        List<Node>[] reverseGraph = new List[n + 1];
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();

        }

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

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());

            graph[A].add(new Node(B, T));
            reverseGraph[B].add(new Node(A, T));
        }

        //x -> 모든 정점으로 가는 최단거리
        Arrays.fill(xToAllDiff, Integer.MAX_VALUE);
        bfs(x, xToAllDiff, graph);

        // x <- 모든정점으로 오는 최단거리
        Arrays.fill(AllToXDiff, Integer.MAX_VALUE);
        bfs(x, AllToXDiff, reverseGraph);

        // 오고 가는데 가장 오래걸리는 소요시간 구하기
        // 모든 정점 -> x 까지 최단거리
        int max = 0;
        for (int i = 1; i <= n; i++) {
            // i -> x + x -> i 까지 가는데 최단거리의 합중 최댓값을 갱신
            if (AllToXDiff[i] + xToAllDiff[i] > max) {
                max = AllToXDiff[i] + xToAllDiff[i];
            }
        }

        System.out.println(max);
    }

    private static void bfs(int start, int[] diff, List<Node>[] graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        boolean[] visited = new boolean[n + 1];
        pq.add(new Node(start, 0));
        diff[start] = 0;

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (visited[current.idx]) continue;
            visited[current.idx] = true; // 우선순위 큐를 사용했으므로 이미 최솟값임 따라서 방문처리

            List<Node> list = graph[current.idx];
            for (Node node : list) {

                if (diff[node.idx] > node.cost + diff[current.idx]) {
                    diff[node.idx] = node.cost + diff[current.idx];
                    pq.add(new Node(node.idx, diff[node.idx]));
                }
            }

        }

    }
}

❗ 오답노트 / 필요한 지식

1.