그래프/파티 백준 1238번

알고리즘 : 그래프, 다익스트라, 그리디, 다이나믹 프로그래밍

 

파티

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

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

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

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

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

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

 

출력

첫 번째 줄에 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

예제 출력

10

 

 

---

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐서 다른 노드로 가는 경우를 계산하여 최단 거리 테이블을 갱신

5. 위 과정에서 3~4번을 반복

 

 

import java.io.*;
import java.util.*;


public class Main {
    public static class Node {
        private int index;
        private int distance;
        
        public Node(int idex, int distance) {
            this.index = idex;
            this.distance = distance;
        }
        
        public int getIndex() {
            return this.index;
        }
        
        public int getDistance() {
            return this.distance;
        }
    
    }

    private static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    private static final int MAX = 1010;
     
    private static int N, M, X;
  
    private static ArrayList<ArrayList<Node>> g = new ArrayList<ArrayList<Node>>();
    private static ArrayList<ArrayList<Node>> rg = new ArrayList<ArrayList<Node>>();
    private static boolean[] visited = new boolean[MAX];
    
    // 고정된 노드에서 to 까지의 거리
    private static int[] d = new int[MAX];
    
    // 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
    private static int getSmallestNode() {
        int min = INF;
        int idx = 1;
        for (int i=1;i<=N;i++) {
            if(!visited[i] && d[i] < min) {
                min = d[i];
                idx = i;
            }
        }
        return idx;
    }
    
    private static void dijkstra(int start) {
        d[start] = 0;
        visited[start] = true;
        for(Node node: g.get(start-1)) {
            d[node.getIndex()] = node.getDistance();
        }
        
        for(int i=1;i<= N-1; i++) {
            int idx = getSmallestNode();
            visited[idx] = true;
            for(Node node: g.get(idx-1)) {
                int cur = d[idx] + node.getDistance();
                if(cur < d[node.getIndex()]) {
                    d[node.getIndex()] = cur;
                }
            }
        }
    }
    
    
    
    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());
      
      for(int i=1;i<=N;i++) {
          g.add(new ArrayList<Node>());
          rg.add(new ArrayList<Node>());
      }
      
      for(int i=1;i<=M;i++) {
          st = new StringTokenizer(br.readLine());
          int from = Integer.parseInt(st.nextToken());
          int to = Integer.parseInt(st.nextToken());
          int distance = Integer.parseInt(st.nextToken());
          Node node = new Node(to, distance);
          g.get(from-1).add(node);
      }
      
      int[] toTarget = new int[N+1];
      // 목표 지점까지 가는 최단 거리
      for(int i=1;i<=N;i++) {
          if(i != X) {
               Arrays.fill(d, INF);
               Arrays.fill(visited, false);
               dijkstra(i);
               toTarget[i] = d[X];
          }
      }
      
      Arrays.fill(d, INF);
      Arrays.fill(visited, false);
      // 목표 지점에서 각 마을 까지 돌아가는 최단거리
      dijkstra(X);
      int max = 0;
      
      // 목표 지점까지 오고 가는데 가장 많은 소요 시간 구하기.
      for(int i=1;i<=N;i++) {
          if(i != X) {
              int sum = toTarget[i] + d[i];
              if(sum > max) {
                  max = sum;
              }
          }
      }
      
      System.out.println(max);
      
    }
}

 

 

 

참조

- 다익스트라 알고리즘 : https://www.youtube.com/watch?v=611B-9zk2o4 

- 다익스트라 알고리즘 : https://www.youtube.com/watch?v=F-tkqjUiik0 

- 백준 1238번 : https://www.acmicpc.net/problem/1238