백준 [자바 java] 1238번 : 지름길

개념공부만 하니까 좀 지겨워서 백준을 풀었다.

 

문제설명

https://www.acmicpc.net/problem/1238

n명의 사람들이 있고, 그 사람들 사이를 지나다닐 때 걸리는 시간이 주어졌을 때, n명의 사람들 중 특정 사람(x)를 오고가는데 걸리는 시간이 가장 많은 사람의 시간을 구하는 문제이다

 

뭔가 외국어를 번역한 문제라 처음엔 이해가 좀 어려웠는데

그냥 x까지 왕복하는 각각의 사람들에 대한 최소비용을 계산하고 이 최소비용의 최댓값을 구하면 되는 문제이다.

 

코드

package org.example;
import java.io.*;
import java.util.*;

public class Main {

  public static ArrayList<ArrayList<Node>> rode;
  public static int[][] ans;

  static class Node implements Comparable<Node> {
    int nodeNum;
    int time;

    public Node(int nodeNum,int time){
      this.nodeNum = nodeNum;
      this.time = time;
    }

    @Override
    public int compareTo(Node node){
      return this.time - node.time;
    }
  }

  public static void ds(int n){
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(n,0));

    while(pq.size() != 0){
      Node now = pq.poll();
      if(ans[n][now.nodeNum] < now.time) continue;

      ArrayList<Node> nowList = rode.get(now.nodeNum);

      for(int i = 0;i<nowList.size();i++){
        if(ans[n][nowList.get(i).nodeNum] > now.time + nowList.get(i).time){
          ans[n][nowList.get(i).nodeNum] = now.time + nowList.get(i).time;
          pq.add(new Node(nowList.get(i).nodeNum, now.time + nowList.get(i).time));
        }
      }
    }

  }

  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    rode = new ArrayList<>();

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int x = Integer.parseInt(st.nextToken());

    ans = new int[n+1][n+1];

    for(int i = 0;i<=n;i++){
      rode.add(new ArrayList<>());
      for(int j = 0;j<=n;j++){
        ans[i][j] = Integer.MAX_VALUE;
      }
    }

    for(int i = 0;i<m;i++){
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      int cost = Integer.parseInt(st.nextToken());
      rode.get(start).add(new Node(end,cost));
    }

    for(int i = 1;i<=n;i++){
      ds(i);
    }

    int max = 0;

    for(int i = 1;i<=n;i++){
      if(i == x) continue;
      if(max < ans[x][i] + ans[i][x]){
        max = ans[x][i] + ans[i][x];
      }
    }

    System.out.println(max);


  }
}

 

전체 코드는 위와 같다.

 

나는 다익스트라 개념을 사용했다. 다익스트라 함수에서 파라미터로 사람을 의미하는 정수를 받으면, 그 사람에 대해서 n명의 사람들을 방문하는데 드는 최소비용을 구한다.

 

이런식으로 모두 탐색하여 2차원배열에 모든 경우의 수를 저장하고 ,x까지 왕복하는 시간의 최댓값을 구해서 출력하면 된다.

 

실수했던 부분

• 처음에 다익스트라에서 이미 방문한 노드이면 continue 해야하는데 break라고 함
• 거리 갱신되었으면 다시 큐에 해당 노드 넣어야하는데 안넣음
• 처음에 배열을 maxValue로 설정했기 때문에 x노드에서 x노드까지 가는데 걸리는 시간이 maxValue로 설정될 수 있음 그래서 마지막에 최댓값 구할 때에는 x노드에서 x노드로 가는 건 배제하고 계산했다

오랜만에 하니까 패키지 코드 지우는거 까먹었다..