[알고리즘] 백준 > #1238. 파티

문제링크

백준 #1238. 파티

풀이방법

보자마자 최단거리! 다익스트라! 까지 생각나는 문제입니다. 근데 일반적인 다익스트라와 달리 돌아오는 거리까지 고려해야하죠? 따라서, y도시 -> x도시 -> y도시 == (y도시 -> x도시) + (x도시 -> y도시) 값을 구해야합니다!

x는 하나로 고정되어 있지만 이 값이 최대가 되는 x를 구해야하는 문제입니다. 그럼 (x도시 -> y도시)는 다익스트라 한 방에 모든 도시에 대한 값을 구할 수 있는데 (y도시 -> x도시)는 어떻게 해야할까요? 단방향 도로의 방향을 바꾸면 됩니다! 원래 (y도시 -> x도시) 값은 단방향 도로의 방향을 바꾼 (x도시 -> y도시)와 동일해집니다! 그럼 이것도 다익스트라 한 방에 구할 수 있겠네요 ㅎㅎ 다익스트라 두 번에 해결할 수 있는 문제였습니다~

코드

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ1238 {
    static boolean[] visited = new boolean[1000];
    static PriorityQueue<Town> pq = new PriorityQueue<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt() - 1;

        LinkedList<Road>[] graph = new LinkedList[n];
        LinkedList<Road>[] reversedGraph = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
            reversedGraph[i] = new LinkedList<>();
        }

        while (--m >= 0) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            int time = sc.nextInt();

            graph[a].add(new Road(b, time));
            reversedGraph[b].add(new Road(a, time));
        }

        int[] costs = new int[n];
        initVariable(n, costs);
        costs[x] = 0;
        pq.offer(new Town(x, 0));
        costs = getCosts(graph, costs);

        int[] reversedCosts = new int[n];
        initVariable(n, reversedCosts);
        reversedCosts[x] = 0;
        pq.offer(new Town(x, 0));
        reversedCosts = getCosts(reversedGraph, reversedCosts);

        int maxValue = 0;
        for (int i = 0; i < n; i++) if (maxValue < (costs[i] + reversedCosts[i])) maxValue = costs[i] + reversedCosts[i];
        System.out.print(maxValue);
    }

    private static void initVariable(int n, int[] costs) {
        for (int i = 0; i < n; i++) {
            costs[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }
    }

    private static int[] getCosts(LinkedList<Road>[] graph, int[] costs) {
        if (pq.isEmpty()) return costs;

        Town head = pq.poll();
        if (!visited[head.id]) {
            for (Road road: graph[head.id]) {
                if (costs[road.dest] > (costs[head.id] + road.cost)) {
                    costs[road.dest] = costs[head.id] + road.cost;
                    pq.offer(new Town(road.dest, costs[road.dest]));
                }
            }
            visited[head.id] = true;
        }

        return getCosts(graph, costs);
    }
}

class Road {

    public int dest;
    public int cost;

    public Road(int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }
}

class Town implements Comparable<Town> {

    public int id;
    public int cost;

    public Town(int id, int cost) {
        this.id = id;
        this.cost = cost;
    }

    @Override
    public int compareTo(Town o) {
        return this.cost - o.cost;
    }
}