[BOJ] 1238. 파티

[작성일]

• 2022-02-24

[분류]

• 다익스트라
  
  
  

[문제링크]

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

[요구사항]

• N명의 사람이 X까지 갔다가 돌아오는데, 이 때 걸리는 cost가 가장 많은 사람의 cost를 구하라.
  
  
  

[풀이]

우선 문제를 보자마자 다익스트라가 떠올라서 모든 사람들(1~N)에 대해서 다익스트라를 수행해줘서 X까지 cost를 구하고 X에서 다른 사람들에 대한 cost까지 모두 구해졌으니 이를 가지고 계산을 해보았다. 하지만 메모리초과가 떴다.

메모리초과가 딱히 날 부분은 못 느꼈고, 모든 경우를 다 계산해주어야하는 것이 비효율적일 것이라고 생각했다. 그래서 더 적게 수행해야하는 방법을 고민하다가 반대로 단방향 그래프 만들기라는 방법을 알게되었다. 어짜피 다른 모든 노드에서 오직 X로만 가는 것만 구하면 되는데 이를 구하기 위해서 반대로 그래프를 만들고 X에서 다익스트라를 사용해서 훨씬 시간과 공간 모두 단축할 수 있었다.

[코드]

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

public class Main {
    static int N, M, X;
    static int[] toX;
    static int[] fromX;

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

        // X에서 다른 점으로 까지 거리를 구하기 위한 list
        // 다른 점에서 X까지 거리를 구하기위한 list2
        ArrayList<Edge>[] list = new ArrayList[N + 1];
        ArrayList<Edge>[] list2 = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            list2[i] = new ArrayList<>();
        }

        // 그래프 입력
        int u, v, w;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            list[u].add(new Edge(v, w));
            list2[v].add(new Edge(u, w));
        }

        // 1. X에서 다른 곳으로 까지 최소거리
        fromX = new int[N + 1];
        Arrays.fill(fromX, Integer.MAX_VALUE);
        dijkstra(X, fromX, list);

        // 2. 다른 점에서 X까지 최소거리 = X에서 다른점까지로 똑같이 다익스트라를 쓰되, 단방향그래프를 반대로 만들기
        toX = new int[N + 1];
        Arrays.fill(toX, Integer.MAX_VALUE);
        dijkstra(X, toX, list2);

        int ans = 0;
        for(int i = 1; i <= N; i++) {
            ans = Math.max(ans, toX[i] + fromX[i]);
        }
        System.out.println(ans);
    }

    public static void dijkstra(int start, int[] distance, ArrayList<Edge>[] list) {
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.cost < o2.cost) return 1;
                else if (o1.cost == o2.cost) return 0;
                else return -1;
            }
        });
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            if (now.cost > distance[now.node]) continue;
            for (Edge next : list[now.node]) {
                // 안되는 조건일 때 넘어가기
                if (distance[next.node] > next.cost + distance[now.node]) {
                    distance[next.node] = next.cost + distance[now.node];
                    pq.add(new Edge(next.node, distance[next.node]));
                }
            }
        }
    }
}

class Edge {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
}