P.1238 파티

코드

1. (잘못된) 다익스트라

package Baekjoon.Class;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class P_1238 {

    static int n;
    static ArrayList<Node>[] graph;

    static class Node {
        int edge;
        int time;

        public Node(int edge, int time) {
            this.edge = edge;
            this.time = time;
        }
    }

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

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; int m = line[1], x = line[2];
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph[line[0]].add(new Node(line[1], line[2]));
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            int time = dijkstra(i, x);
            time += dijkstra(x, i);

            max = Math.max(max, time);
        }

        bw.write(Integer.toString(max));
        bw.flush();
    }

    private static int dijkstra(int start, int end) {
        int[] times = new int[n + 1];
        Arrays.fill(times, Integer.MAX_VALUE);
        times[start] = 0;

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(new Node(start, 0));

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

            for (Node node : graph[poll.edge]) {
                if (times[node.edge] > poll.time + node.time) {
                    times[node.edge] = poll.time + node.time;
                    queue.add(new Node(node.edge, poll.time + node.time));
                }
            }
        }

        return times[end];
    }
}

2. bfs

package Baekjoon.Class;

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

public class P_1238 {

    static int n;
    static ArrayList<Node>[] graph;

    static class Node {
        int edge;
        int time;

        public Node(int edge, int time) {
            this.edge = edge;
            this.time = time;
        }
    }

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

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; int m = line[1], x = line[2];
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph[line[0]].add(new Node(line[1], line[2]));
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            int time = bfs(i, x);
            time += bfs(x, i);

            max = Math.max(max, time);
        }

        bw.write(Integer.toString(max));
        bw.flush();
    }

    private static int bfs(int start, int end) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparing(o -> o.time));
        queue.add(new Node(start, 0));
        boolean[] visited = new boolean[n + 1];

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

            if (poll.edge == end) return poll.time;

            if (!visited[poll.edge]) {
                visited[poll.edge] = true;
                for (Node node : graph[poll.edge]) {
                    if (!visited[node.edge])
                        queue.add(new Node(node.edge, poll.time + node.time));
                }
            }
        }
        return -1;
    }
}

3. 다익스트라

package Baekjoon.Class;

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

public class P_1238 {

    static int n;

    static class Node {
        int edge;
        int time;

        public Node(int edge, int time) {
            this.edge = edge;
            this.time = time;
        }
    }

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

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; int m = line[1], x = line[2];
        ArrayList<Node>[] graph = new ArrayList[n + 1];
        ArrayList<Node>[] reverseGraph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph[line[0]].add(new Node(line[1], line[2]));
            reverseGraph[line[1]].add(new Node(line[0], line[2]));
        }

        int[] time1 = dijkstra(x, graph);
        int[] time2 = dijkstra(x, reverseGraph);

        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, time1[i] + time2[i]);
        }

        bw.write(Integer.toString(max));
        bw.flush();
    }

    private static int[] dijkstra(int start, ArrayList<Node>[] targetGraph) {
        int[] times = new int[n + 1];
        Arrays.fill(times, Integer.MAX_VALUE);
        times[start] = 0;

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(new Node(start, 0));

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

            for (Node node : targetGraph[poll.edge]) {
                if (times[node.edge] > poll.time + node.time) {
                    times[node.edge] = poll.time + node.time;
                    queue.add(new Node(node.edge, poll.time + node.time));
                }
            }
        }

        return times;
    }
}

코드 설명

출발지에서 목적지까지의 거리를 구하는 문제이므로 bfs를 이용했다.

사실 처음에는 다익스트라로 풀었는데 처음 풀이한 다익스트라는 다익스트라 느낌보다는 bfs에 가깝다.

bfs로도 정답이 나오긴하지만 메모리상이나 시간상으로나 마음에 들지 않아서 정석적인 다익스트라로 다시 풀었다.

 

1번부터 n번까지의 사람이 X를 왕복하는 방법은 다음과 같다.

n번에서 X로 가는데 걸리는 시간 + X에서 n번으로 가는데 걸리는 시간

 

먼저 n번에서 X로 가는데 걸리는 시간을 다익스트라로 구해보자.

다익스트라는 출발점이 정해져있는 알고리즘이다.

하지만 n번에서 X로 가는데 걸리는 시간을 구할 때 출발점은 계속해서 달라진다.

이 출발점을 for문으로 다르게 해서 다익스트라를 구하게 된다면 1번 코드가 된다 ㅋㅋ.

그럼 출발점을 X로 바꾸면 된다. 

 

결국 'X에서 n번으로 가는데 걸리는 시간'을 2번 계산하게 되며 입력값을 반대로 저장하는 그래프를 하나 더 생성하면 된다.

graph[line[0]].add(new Node(line[1], line[2]));
reverseGraph[line[1]].add(new Node(line[0], line[2]));

 

이렇게 할 경우 표면적으로 'n번에서 X로 가는데 걸리는 시간 + X에서 n번으로 가는데 걸리는 시간'을 구한 것처럼 보인다.

또 n번에서 X로 가는데 걸리는 시간을 한번의 다익스트라 알고리즘으로 구할 수 있고, 반대도 마찬가지로 한 번으로 구할 수 있으므로 시간도 훨씬 절약된다.