[Java] 백준 1238번 : 파티

문제소개

 

해결과정

다익스트라 문제이다.

1 ~ N번 노드가 존재하며, 특정 X 노드를 지정해 다른 노드에 있는 사람들은 모두 X 노드로 왔다가 다시 제자리로 돌아가야한다.

이 때, 노드 사이에는 가중치가 있는 간선이 존재한다. *단방향 간선이기 때문에 가는 길과 오는 길이 다를 수 있다.*

X번 노드를 제외한 다른 모든 노드에서 X 노드를 방문했다가 다시 돌아올 때 최단 거리를 구해야하고, 모든 노드 중 최단 거리가 가장 큰 노드를 찾아내면 된다.

 

문제 풀이의 핵심은 다익스트라를 총 2번 활용해 풀이해내는 것이다. (1 : 임의의 노드 -> X 노드, 2 : X 노드 -> 임의의 노드)

X 노드에서 각 노드로 가는 최단거리는 X 노드를 시작으로 하는 다익스트라를 구성하면 된다.

 

문제는 반대 방향에서 발생한다.

임의의 노드에서 X 노드로 가는 최단거리를 구하려면 임의의 노드를 시작 지점으로 하는 다익스트라를 N - 1번 돌리면 될까?

물론 이론상으로는 정답을 구할 수 있을 것이다. 하지만 주어진 노드의 크기와 간선을 고려한다면 시간초과가 발생할 가능성이 있기에 

추가적으로 단 한번의 다익스트라를 통해 임의의 노드에서 X 노드로 최단거리를 모두 구할 수 있어야한다.

 

솔루션은 간단했다. 최초 주어진 간선의 정보 자체가 단방향이기 때문에, *방향을 바꾼 그래프를 추가로 만들어놓으면 된다.*

쉽게 생각해 주어진 간선을 그대로 표현한 정방향 그래프와 방향을 바꾼 역방향 그래프, 총 두 개의 그래프를 생성한다.

 

역방향 그래프를 통해, X 노드를 시작으로하는 다익스트라를 돌린다면 임의의 노드에서 X 노드로 가는 최단거리를 단 한번의 다익스트라 알고리즘을 통해 모두 구할 수 있다!

 

솔루션

public class Main {

    static ArrayList<Node>[] posGraph, nagGraph;
    static int[] posDist, nagDist, result;
    static int N, M, X;

    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());

        posGraph = new ArrayList[N + 1];
        nagGraph = new ArrayList[N + 1];
        posDist = new int[N + 1];
        nagDist = new int[N + 1];
        result = new int[N + 1];
        Arrays.fill(posDist, Integer.MAX_VALUE);
        Arrays.fill(nagDist, Integer.MAX_VALUE);

        for (int i = 0; i <= N; i++) {
            posGraph[i] = new ArrayList<>();
            nagGraph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            posGraph[start].add(new Node(end, cost));
            nagGraph[end].add(new Node(start, cost));
        }

        dijkstra(posDist, posGraph);
        dijkstra(nagDist, nagGraph);

        for (int i = 0; i <= N; i++) {
            result[i] = posDist[i] + nagDist[i];
        }

        int maxValue = Arrays.stream(result)
                .max()
                .orElse(-1);
        System.out.println(maxValue);
    }

    static void dijkstra(int[] dist, ArrayList<Node>[] graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.cost, n2.cost));
        boolean[] visited = new boolean[N + 1];

        pq.add(new Node(X, 0));
        dist[X] = 0;

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

            if (visited[poll.vertex]) continue;
            visited[poll.vertex] = true;

            for (Node node : graph[poll.vertex]) {
                if (dist[node.vertex] > poll.cost + node.cost) {
                    dist[node.vertex] = poll.cost + node.cost;
                    pq.add(new Node(node.vertex, dist[node.vertex]));
                }
            }
        }
    }

    static class Node {
        int vertex;
        int cost;

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