[백준] 1238.파티 - Java

1. 문제

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

 

 

2. 문제 설명

이 문제는 N개 숫자로 구분된 각각의 마을이 존재하며, 각 마을에는 한 명의 학생이 살고있다.

각 마을을 이어주는 시간이 T만큼 걸리는 단방향 도로가 존재한다.

학생들은 파티를 위해 X마을로 모여서 파티하고 끝나며 다시 자기가 살던 마을로 돌아간다.

이 때 각 학생들은 최단 시간을 통해서만 이동한다.

여기서 가장 시간이 오래걸린 학생의 걸린 시간을 출력하는 문제이다.

 

이 문제는 다익스트라 알고리즘을 통해서 해결할 수 있다.

다익스트라를 풀어본 적이 없다면, 아래 문제를 먼저 풀어보는 것을 추천한다.

https://soonmin.tistory.com/179

[백준] 1753. 최단경로 - JAVA

 

이 문제를 푸는 기본 아이디어는 각 마을 i에서 X까지의 최단 거리 + X에서 i까지의 최단 거리가 i 학생의 왕복 시간이다. 

이 중 최댓값을 출력하면 정답으로 처리된다.

 

처음 풀었던 방식 (비효율적)

모든 마을 i에서 X까지 다익스트라를 N번 실행하여 각각의 i 마을에 대한 최단 거리를 구해주었다.

그리고, X 마을에서 모든 마을까지 다익스트라 1번을 실행하여 최단 거리를 구해주었다.

총 다익스트라를 N + 1번 실행하여 왕복거리를 구했다. 

// i 마을 => X
int[] result = new int[N + 1];
for (int i = 1; i <= N; i++) {
    int[] dist = dijkstra(i); // i = 출발지점
    result[i] = dist[X];
}

// X => i 마을
int[] dist = dijkstra(X); // X = 출발지점
for (int i = 1; i <= N; i++) {
    result[i] += dist[i];
}

 

결과는 성공!!

 

전체 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int M;
    static int X;
    static int INF = 10000 * 100;
    static List<List<Point>> graph = new ArrayList<>();

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

        for (int i = 0; i <= N; i++) {
            graph.add(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 t = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Point(end, t));
        }

        // N -> X
        int[] result = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int[] dist = dijkstra(i);
            result[i] = dist[X];
        }

        // X -> N
        int[] dist = dijkstra(X);
        for (int i = 1; i <= N; i++) {
            result[i] += dist[i];
        }

        int max = Arrays.stream(result).max().getAsInt();
        bw.write(max + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static int[] dijkstra(int start) {
        int[] dist = new int[N + 1];
        boolean[] visited = new boolean[N + 1];
        Arrays.fill(dist, INF);

        PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
        pq.offer(new Point(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (visited[cur.x]) {
                continue;
            }
            visited[cur.x] = true;
            for (Point next : graph.get(cur.x)) {
                if (dist[next.x] > dist[cur.x] + next.w) {
                    dist[next.x] = dist[cur.x] + next.w;
                    pq.offer(new Point(next.x, dist[next.x]));
                }
            }
        }

        return dist;
    }

    static class Point {
        int x;
        int w;

        Point(int x, int w) {
            this.x = x;
            this.w = w;
        }
    }
}

 

 

다른 사람 풀이 참고(효율적)

하지만, 다른 사람의 풀이를 보고 내가 작성한 알고리즘은 비효율적이라고 생각하게 되었다.

그래프를 정방향, 역방향 두개로 구성하여 해결할 수 있었다.

toX 는 원래 그래프고, fromX는 간선 방향을 뒤집은 그래프이다.

 

이렇게 그래프를 구성하면 다익스트라를 두 번만 수행하여 왕복거리를 구할 수 있다.

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 t = Integer.parseInt(st.nextToken());
    toX.get(start).add(new Point(end, t));
    fromX.get(end).add(new Point(start, t));
}

int[] toXDist = dijkstra(toX); // N -> X
int[] fromXDist = dijkstra(fromX); // X -> N

 

 

실행 시간이 절반 이상 단축되었다.

 

 

전체 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int M;
    static int X;
    static int INF = 10000 * 100;
    static List<List<Point>> toX = new ArrayList<>();
    static List<List<Point>> fromX = new ArrayList<>();


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

        for (int i = 0; i <= N; i++) {
            toX.add(new ArrayList<>());
            fromX.add(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 t = Integer.parseInt(st.nextToken());
            toX.get(start).add(new Point(end, t));
            fromX.get(end).add(new Point(start, t));
        }

        int[] toXDist = dijkstra(toX); // N -> X
        int[] fromXDist = dijkstra(fromX); // X -> N

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, toXDist[i] + fromXDist[i]);
        }

        bw.write(max + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static int[] dijkstra(List<List<Point>> graph) {
        int[] dist = new int[N + 1];
        boolean[] visited = new boolean[N + 1];
        Arrays.fill(dist, INF);

        PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
        pq.offer(new Point(X, 0));
        dist[X] = 0;

        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (visited[cur.x]) {
                continue;
            }
            visited[cur.x] = true;
            for (Point next : graph.get(cur.x)) {
                if (dist[next.x] > dist[cur.x] + next.w) {
                    dist[next.x] = dist[cur.x] + next.w;
                    pq.offer(new Point(next.x, dist[next.x]));
                }
            }
        }

        return dist;
    }

    static class Point {
        int x;
        int w;

        Point(int x, int w) {
            this.x = x;
            this.w = w;
        }
    }
}