백준 1238 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

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

        //N, M, X 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken())-1;

        //배열 그래프 초기화
        int[][] graph=new int[n][n];
        for(int i=0; i<n; i++) {
            Arrays.fill(graph[i], 100000000);
            graph[i][i]=0;
        }

        //도로 정보 입력 받기
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            graph[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = Integer.parseInt(st.nextToken());
        }

        //{방문 노드, Flag, 현재까지 비용}에서 비용을 기준으로 하는 우선순위큐
        PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[2]));

        //X 마을에서 각 마을까지로 갈 때(0), 올 때(1) 거리 초기화
        //distance[1][1] = 1번 마을에서 X 마을로 올 때의 최소 거리
        //distance[4][0] = X 마을에서 4번 마을로 갈 때의 최소 거리
        int[][] distance=new int[n][2];
        distance[x][0]=0;
        distance[x][1]=0;

        for(int i=0; i<n; i++) {
            distance[i][0] = graph[x][i];
            distance[i][1] =graph[i][x];

            if(distance[i][0]!=100000000)
                pq.add(new int[]{i, 0, distance[i][0]});
            if(distance[i][1]!=100000000)
                pq.add(new int[]{i, 1, distance[i][1]});
        }

        //방문 정보도 갈 때, 올 때로 나눠서 2차원 배열
        boolean[][] visited=new boolean[n][2];
        while(!pq.isEmpty()){
            int[] ptr = pq.poll();

            //방문 노드, 갈 때인지 올 때인지 Flag에 대해서 방문 검사
            if(visited[ptr[0]][ptr[1]])
                continue;
            visited[ptr[0]][ptr[1]]=true;

            for(int i=0; i<n; i++){
                //i번 마을을 갈 때 또는 올 때 방문했으면 continue
                if(visited[i][ptr[1]])
                    continue;

                //X 마을에서 갈 때라면
                if(ptr[1]==0)
                    //graph[현재 마을][i마을]로 최소 거리 갱신
                    if(distance[i][0]>ptr[2]+graph[ptr[0]][i]){
                        distance[i][0]=ptr[2]+graph[ptr[0]][i];
                        pq.add(new int[]{i, 0, distance[i][0]});
                    }
                //X 마을로 올 때라면
                if(ptr[1]==1)
                    //graph[i마을][현재 마을]로 최소 거리 갱신
                    if(distance[i][1]>ptr[2]+graph[i][ptr[0]]){
                        distance[i][1]=ptr[2]+graph[i][ptr[0]];
                        pq.add(new int[]{i, 1, distance[i][1]});
                    }
            }
        }

        int answer=IntStream.range(0, n)
                .map(o->distance[o][0]+distance[o][1])
                .max()
                .getAsInt();
        System.out.println(answer);
    }
}

---

해결 과정

1. Floyd로 푼다면 O(N^3)이 걸리게 된다. 이 문제는 모든 노드에서 X 노드로 가는 최소 거리 + X 노드에서 모든 노드로 가는 최소 거리를 구하는 것이다. 모든 노드에서 X 노드로 가는 최소 거리는 X 노드에서 출발해서 역방향 거리 정보를 가지고 Dijkstra를 하면 되고, X 노드에서 모든 노드로 가는 최소 거리는 X 노드에서 출발해서 정방향 거리 정보를 가지고 Dijkstra를 하면 된다.
   이렇게 한다면 O(N^2)으로 가능하다.

2. 😁