백준 No. 1238 파티 JAVA

 

 

문제

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

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

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

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

 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

 

 

 

문제를 잘못 이해했던 점

다익스트라로 푸는 문제인 건 알겠는데 그래서 결국 x가 2일때 2번 노드에서 가면 되는 게 아닌건가??

는 생각으로 계속 시도했는데 제일 큰 값은 7.... 그 외에는 도저히 나올 수 없었다. 그래서 결국 풀이를 봤는데 해당 문제는 돌아오는 값도 구해야 했던 것이다.

그리고 막상 그래프를 그려보니

이런식이었다. 돌고 돌아 돌아온다.

결국 답을 봐버렸다 돌아오는 길을 하나씩 전부 구하는 게 너무 어려웠었다...

결국 찾은 방법은 주어진 간선을 거꾸로 받는다.

1  2  4  로 주어진다면  1번 노드에서 2번 노드로 간선에 4의 가중치가 있는 형태인데 이를 반대로 하면

2  1  4 이다. 이런식으로 구하여 reversDist[] 배열을 만들고 이런식으로 간선들을 추가로 받아야한다. 

reverseGraph

graph

이렇게 하고 dist[] 배열도 reverse용 배열을 따로만든다. 해당 배열은 인덱스(노드번호)가 2번으로 돌아가는데 걸리는 최단 경로값이 들어간다. 반대로 dist[] 배열은 해당 시작(2번노드)가 가는 모든 배열에 최단경로를 의미한다.

그렇기 때문에 최단경로탐색 메소드에서는 두 메소드를 각각 처리할 수 있는 파라미터를 받고

visited도 두 번 초기화해야한다. 메소드 호출시 초기화하도록 해야한다.

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

public class Main {


    public static int N, M, X; //N 명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로가 있다.,
    private static final int INF = 1000000000;

    static int dist[];

    static int reversDist[];
    static  boolean visited[];
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static ArrayList<ArrayList<Node>> reverseGraph = new ArrayList<>();
    public static void main(String[] args) throws IOException {

        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];

        reversDist = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
            reverseGraph.add(new ArrayList<>());
        }
        
        for (int i = 0; i <M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());   //시작점
            int b = Integer.parseInt(st.nextToken());   //끝점
            int c = Integer.parseInt(st.nextToken());   //가중치

            graph.get(a).add(new Node(b, c));
            reverseGraph.get(b).add(new Node(a, c));
        }

        Arrays.fill(dist,INF);
        Arrays.fill(reversDist,INF);
        result(graph, X, dist);
        result(reverseGraph, X, reversDist);

        print();
    }

    static void result(ArrayList<ArrayList<Node>> nodes,int x,int distance[]) {
        visited = new boolean[N + 1];
        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        queue.add(new Node(x,0));
        distance[x] = 0;

        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(visited[now.v]){
                continue;
            }else{
                visited[now.v] = true;
                for(Node next : nodes.get(now.v)){
                    if(distance[next.v] > distance[now.v] + next.cost) {
                        distance[next.v] = distance[now.v] + next.cost;
                        queue.add(new Node(next.v, distance[next.v]));
                    }
                }
            }
        }
    }
    private static void print() {
        int ans = -1;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist[i] + reversDist[i]);
        }
        System.out.println(ans);
    }
        int v;
        int cost;
        public Node(int v,int cost){
                this.v = v;
                this.cost = cost;
        }
    }
}