[백준] 1238번 : 파티

문제

www.acmicpc.net/problem/1238

1238번: 파티

문제해결방법

처음에는 다른 모든 학생들한테서 X까지의 거리를 알아내기 위해 다익스트라를 해야되는지, 플로이드 워셜을 해야되는지 고민했었다.

그런데 생각해보니까 도로를 뒤집어서 그 뒤집은 도로로 X에서 출발하는 다익스트라를 돌리면 각 학생들이 X로 오는 거리를 구할 수 있다는 걸 알아내서 그 방법으로 풀었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main1238_파티 {
 
    public static int N, M, X;
    public static int[] dist, reverseDist;
    public static List<int[]>[] edge, reverseEdge;
    public static PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
        @Override
        public int compare(int[] arg0, int[] arg1) {
            return Integer.compare(arg0[1], arg1[1]);
        }
    });
    
    public static void main(String[] args) throws Exception {
        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());
        dist = new int[N+1];
        reverseDist = new int[N+1];
        edge = new List[N+1];
        reverseEdge = new List[N+1];
        for(int i=1; i<=N; i++) {
            edge[i] = new ArrayList<>();
            reverseEdge[i] = new ArrayList<>();
            if(i==X) continue;
            dist[i] = Integer.MAX_VALUE;
            reverseDist[i] = Integer.MAX_VALUE;
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edge[s].add(new int[] {e, v});
            reverseEdge[e].add(new int[] {s, v});
        }
        pq.add(new int[] {X, 0});
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            for(int i=0; i<edge[cur[0]].size(); i++) {
                int[] next = edge[cur[0]].get(i);
                if(dist[next[0]]>cur[1]+next[1]) {
                    dist[next[0]]=cur[1]+next[1];
                    pq.add(new int[] {next[0], dist[next[0]]});
                }
            }
        }
        pq.add(new int[] {X, 0});
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            for(int i=0; i<reverseEdge[cur[0]].size(); i++) {
                int[] next = reverseEdge[cur[0]].get(i);
                if(reverseDist[next[0]]>cur[1]+next[1]) {
                    reverseDist[next[0]]=cur[1]+next[1];
                    pq.add(new int[] {next[0], reverseDist[next[0]]});
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=N; i++) {
            if(i==X) continue;
            if(max<dist[i]+reverseDist[i]) max=dist[i]+reverseDist[i];
        }
        System.out.println(max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.