1238번: 파티 (골드 3)

1238번: 파티 (acmicpc.net)

1238번: 파티

1. 문제 설명

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.

(2) 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간

Ti가 들어온다.

(3) 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

(4) 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

 

출력 조건

(1) 첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

입출력 예제

 

 

 

3. 풀이 및 코드

: 이 문제는 다익스트라를 활용하여 푸는 문제이다.

( 다익스트라 설명은 아래 링크로 )

다익스트라 (Dijkstra) (tistory.com)

 

( 이 문제는 위 링크대로 풀어도 되지만, 우선순위 큐를 사용하면, 메모리를 보다 효율적으로 그리고 시간을 더 빠르게 

수행할 수 있다. )

( 또한 우선순위 큐를 사용할려면, 정렬이 필요한데, Node 클래스를 따로 만들어 Comparable의 compareTo()를 받아

구현한다. )

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Node implements Comparable<Node>{
    int end, weight;
    
    Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
 
    // 우선순위 큐에서 최솟값으로 정렬
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
    
}
 
public class Main {
    static int N, M, X;
    static ArrayList<Node>[] list1, list2;
 
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(sc.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        
        list1 = new ArrayList[N+1];
        list2 = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            list1[i] = new ArrayList<>();
            list2[i] = new ArrayList<>();
        }
        
        for(int i=1; i<=M; i++) {
            st = new StringTokenizer(sc.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            
            list1[a].add(new Node(b, t));
            list2[b].add(new Node(a, t));
        }
        int[] dist1 = solve(X, list1);
        int[] dist2 = solve(X, list2);
        
        int max=0;
        for(int i=1; i<=N; i++) {
            max = Math.max(max, dist1[i]+dist2[i]);
        }
        System.out.println(max);
    }
    
    static int[] solve(int start, ArrayList<Node>[] arr) {
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        boolean[] visited = new boolean[N+1];
        
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start] = 0;
        
        while(!q.isEmpty()) {
            Node curNode = q.poll();
            start = curNode.end;
            
            if(visited[start]) continue;
            visited[start] = true;
            
            for(Node node : arr[start]) {
                if(dist[node.end] > dist[start]+node.weight) {
                    dist[node.end] = dist[start]+node.weight;
                    q.add(new Node(node.end, dist[node.end]));
                }
            }
        }
        return dist;
    }
}