[백준 1238] - 파티 Java

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

 

1238번: 파티

풀이

문제를 요약하면

각 마을의 학생들이

X번 마을에서 열리는 파티에 참여하고 돌아가는 길의 최단거리들을 찾고

그 최단거리 중 가장 오래 걸리는 학생의 소요 시간을 출력하면 된다.

다시 말해서 n→$X$+ $X$→n의 소요 시간의 최댓값을 구하는 것이다.

주의할 점은 단방향 그래프이기 때문에 파티로 가는 경로와 집으로 오는 경로가 다를 수 있다.

예시

3번 마을의 학생이 $X$(2)번 마을에서 열리는 파티에 참여하는 최소 비용 경로는

3 - 1 - 2이고, 소요 시간은 2 + 4 = 6이다.

$X$2)번 마을에서 다시 3번 마을로 돌아가는 최소 비용 경로는

2-1-3이고, 소요 시간은 1 + 2 = 3이다.

이 때의 소요시간은 총 9가 된다.

원래는 틀린 풀이?? (플로이드-와샬)

처음 문제를 풀 때에는 전체 학생들의 경로를 구해야한다고 판단하고 플로이드-와샬로 구현했다.

하지만 일반적으로 $N$이 최대 1000이기 때문에 $O(n^3)$의 시간 복잡도를 가지는 플로이드-와샬은 1초 이내에 통과할 수 없기 때문에 해당 답안은 정석 풀이가 아니지만 백준에서 정답처리가 되기는 한다…???

package 백준_2024년.백준_1월_1주;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class baekjoon1238_파티 {
    static final int MAX = Integer.MAX_VALUE/2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[][] map = new int[N + 1][N + 1];
        for(int i= 1;i<=N;i++) {
            Arrays.fill(map[i],MAX);
            map[i][i] = 0;

        }
        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 weight = Integer.parseInt(st.nextToken());

            map[start][end] = weight;
        }

        int max = 0;
        for(int k = 1;k<=N;k++) {
                for (int i = 1; i <= N; i++) {
                    if (map[i][k] != MAX) {
                    for (int j = 1; j <= N; j++) {
                        map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);

                    }
                }
            }
        }
        for(int i= 1;i<=N;i++) {
            max = Math.max(max, map[i][X]+map[X][i]);

        }
        System.out.println(max);
    }

}

정석 풀이

1. X로 가는 최단 경로 구하기

일단, 가장 먼저 각 마을의 학생들이 모두$X$로 가는 최단 경로를 찾아야한다.

단순하게 생각하면 각 마을의 학생 n→ $X$를 찾는 다익스트라라고 생각할 수도 있지만, 조금 생각을 바꿔서

$X$로 시작하는 다익스트라를 실행하면 $X$에서 다른 모든 정점으로 가는 최단 경로를 찾을 수 있게 된다. 하지만 이렇게 하면 $X$에서 집으로 가는 경로가 구해지게 되는데, 단방향 그래프이기 때문에 start→end 방향을 뒤집은 그래프가 필요하다.

 

💡 만약 1→4→2, 2→3로 연결된 상황일 때

2에서 다익스트라를 시작하면 $X$에서 집으로 가는 경로가 된다.

지금은 각 마을에서 $X$로 가는 경로를 찾아야하니깐, 2→4→1, 3→2의 그래프로 뒤집어주면 해결된다.

int[][] map = new int[N + 1][N + 1];
int[][] reverseMap = new int[N + 1][N + 1];
for(int i= 1;i<=N;i++) {
    Arrays.fill(map[i],MAX);
    Arrays.fill(reverseMap[i],MAX);
    map[i][i] = 0;
    reverseMap[i][i] = 0;
}

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 weight = Integer.parseInt(st.nextToken());

    map[start][end] = weight;
    reverseMap[end][start] = weight;
}

이후 $X$에서 각 마을의 최단 경로를 찾기 위해 $X$에서 시작하는 다익스트라 알고리즘을 수행한다.

int[] toParty = new int[N + 1];
Arrays.fill(toParty, MAX);
pq = new PriorityQueue<>();
pq.add(new Point(X, 0));

while(!pq.isEmpty()) {
    final Point now = pq.poll();

    if(toParty[now.next]<now.weight) {
        continue;
    }
    toParty[now.next] = now.weight;
    for(int i =1 ;i<=N;i++) {
        if(toParty[i]>now.weight+reverseMap[now.next][i]) {
            pq.add(new Point(i, now.weight+reverseMap[now.next][i]));
        }
    }
}

위 코드의 결과로 각 마을에는 X로 가는 최단 경로가 담기게 된다.

2. X에서 집으로 돌아가는 최단 경로 구하기

이제 X에서 각 집으로 가는 최단 경로는 기존 그래프의 시작점에서 시작만하면 해결된다.

이건 기존 그래프에서 다익스트라 한 번으로 해결된다.

int[] toHome = new int[N + 1];
Arrays.fill(toHome, MAX);
PriorityQueue<Point> pq = new PriorityQueue<>();
pq.add(new Point(X, 0));

while(!pq.isEmpty()) {
    final Point now = pq.poll();

    if(toHome[now.next]<now.weight) {
        continue;
    }
    toHome[now.next] = now.weight;
    for(int i =1 ;i<=N;i++) {
        if(toHome[i]>now.weight+map[now.next][i]) {
            pq.add(new Point(i, now.weight+map[now.next][i]));
        }

    }
}

3. 합의 최댓값 구하기

이건 단순하게 toHome과 toParty의 같은 인덱스끼리 더한 값의 최댓값을 구하면된다.

int max = 0;
for(int i =1 ;i<=N;i++) {
    max = Math.max(toHome[i] + toParty[i], max);
}

전체 코드

package 백준_2024년.백준_1월_1주;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class baekjoon1238_파티_다익스트라 {
    static final int MAX = Integer.MAX_VALUE/2;

    static class Point implements Comparable<Point>{
        int next,weight;

        public Point(int next, int weight) {
            this.next = next;
            this.weight = weight;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[][] map = new int[N + 1][N + 1];
        int[][] reverseMap = new int[N + 1][N + 1];
        for(int i= 1;i<=N;i++) {
            Arrays.fill(map[i],MAX);
            Arrays.fill(reverseMap[i],MAX);
            map[i][i] = 0;
            reverseMap[i][i] = 0;
        }

        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 weight = Integer.parseInt(st.nextToken());

            map[start][end] = weight;
            reverseMap[end][start] = weight;
        }

        int[] toHome = new int[N + 1];
        Arrays.fill(toHome, MAX);
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(X, 0));

        while(!pq.isEmpty()) {
            final Point now = pq.poll();

            if(toHome[now.next]<now.weight) {
                continue;
            }
            toHome[now.next] = now.weight;
            for(int i =1 ;i<=N;i++) {
                if(toHome[i]>now.weight+map[now.next][i]) {
                    pq.add(new Point(i, now.weight+map[now.next][i]));
                }

            }
        }

        int[] toParty = new int[N + 1];
        Arrays.fill(toParty, MAX);
        pq = new PriorityQueue<>();
        pq.add(new Point(X, 0));

        while(!pq.isEmpty()) {
            final Point now = pq.poll();

            if(toParty[now.next]<now.weight) {
                continue;
            }
            toParty[now.next] = now.weight;
            for(int i =1 ;i<=N;i++) {
                if(toParty[i]>now.weight+reverseMap[now.next][i]) {
                    pq.add(new Point(i, now.weight+reverseMap[now.next][i]));
                }
            }
        }
        int max = 0;
        for(int i =1 ;i<=N;i++) {
            max = Math.max(toHome[i] + toParty[i], max);
        }
        System.out.println(max);
    }
}