[BOJ] 11779 최소 비용 구하기 2 - JAVA

1. 문제

11779번: 최소비용 구하기 2

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

---

2. 풀이

Node 클래스

버스 노선을 저장하는 클래스다.

도착 도시, 비용, 현재 도시에서 갈 수 있는 다음 도시를 담는다.

private static class Node {
   int to, cost;
   Node next;

   Node(int to, int cost, Node next) {
      this.to = to;
      this.cost = cost;
      this.next = next;
   }
}

 

Route 클래스

다익스트라 탐색 중 사용하려고 만든 클래스다.

몇 개의 도시를 거쳐야하는지(count), 몇 번 도시인지(city), 얼마의 비용이 걸렸는지(cost) 저장한다.

이전 도시 정보도 저장한다.(편의상 next로 이름지었다.)

private static class Route {
   int count, city, cost;
   Route next;
   Route(int city, int count, int cost, Route next){
      this.city = city;
      this.count = count;
      this.cost = cost;
      this.next = next;
   }
}

 

정답 출력

파라미터로 받은 now는 도착도시다. 도착도시로 가기까지의 비용, 거친 도시 개수를 sb에 추가한다.

도시 경로를 담을 int 배열을 now.count개수 크기로 만들고, 인덱스 역순으로 도시 번호를 저장한다.

sb에는 인덱스 순서대로 추가한다.

sb를 string으로 바꿔서 반환한다.

private static String getResult(Route now) {
   StringBuilder res = new StringBuilder();
   res.append(now.cost).append('\n');
   res.append(now.count).append('\n');

   int[] tmp = new int[now.count];
   for(int i=tmp.length-1;i>=0;i--){
      tmp[i] = now.city;
      now = now.next;
   }

   for (int j : tmp) res.append(j).append(' ');

   return res.toString();
}

 

다익스트라

최대값은 도시 최대 개수 1000개 * 버스 최대 비용 100000원을 곱한 뒤 1을 더한 것이다.

기본적인 다익스트라 풀이지만, pq에 들어갈 객체가 Route다.

따라서 초기값으로 new Route(start,1,0,null)을 넣고 시작한다. start 도시, 도시개수 1개, 비용 0원, 이전 도시가 없다는 의미다.

탐색 중 now.city가 end와 동일하다면 getResult메서드를 부르고 그 값을 바로 반환한다.

pq의 다음 값을 추가할 때 now.count+1하는 것을 잊으면 안된다!

private static String dijkstra(int N, int start, int end, Node[] edges) {
   int INF = 100_000_001;//도시 개수 1,000 * 버스 비용 100,000

   int[] dist = new int[N + 1];
   boolean[] visited = new boolean[N + 1];
   Arrays.fill(dist, INF);
   dist[start] = 0;

   PriorityQueue<Route> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
   pq.offer(new Route(start,1,0,null));

   Route now;
   while (!pq.isEmpty()) {
      now = pq.poll();
      if (visited[now.city]) continue;
      visited[now.city] = true;
      dist[now.city] = now.cost;

      if(now.city==end){
         return getResult(now);
      }

      for (Node node = edges[now.city]; node != null; node = node.next) {
         if (dist[node.to] <= node.cost + now.cost) continue;
         dist[node.to] = node.cost + now.cost;
         pq.offer(new Route(node.to,now.count+1, dist[node.to], now));
      }
   }

   return "";
}

 

Main

방향이 있는 간선이므로 bus[from]에만 간선정보를 추가한다.

dijkstra 메서드의 결과값을 바로 출력한다.

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

   int N = Integer.parseInt(in.readLine());
   int M = Integer.parseInt(in.readLine());
   Node[] bus = new Node[N + 1];

   int from, to, cost;
   for (int i = 0; i < M; i++) {
      st = new StringTokenizer(in.readLine());
      from = Integer.parseInt(st.nextToken());
      to = Integer.parseInt(st.nextToken());
      cost = Integer.parseInt(st.nextToken());
      bus[from] = new Node(to, cost, bus[from]);
   }

   st = new StringTokenizer(in.readLine());
   int start = Integer.parseInt(st.nextToken());
   int end = Integer.parseInt(st.nextToken());

   System.out.println(dijkstra(N, start, end, bus));
}

 

전체 코드

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

public class BOJ_11779_최소비용구하기2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      int N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());
      Node[] bus = new Node[N + 1];

      int from, to, cost;
      for (int i = 0; i < M; i++) {
         st = new StringTokenizer(in.readLine());
         from = Integer.parseInt(st.nextToken());
         to = Integer.parseInt(st.nextToken());
         cost = Integer.parseInt(st.nextToken());
         bus[from] = new Node(to, cost, bus[from]);
      }

      st = new StringTokenizer(in.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());

      System.out.println(dijkstra(N, start, end, bus));
   }

   private static String dijkstra(int N, int start, int end, Node[] edges) {
      int INF = 100_000_001;//도시 개수 1,000 * 버스 비용 100,000

      int[] dist = new int[N + 1];
      boolean[] visited = new boolean[N + 1];
      Arrays.fill(dist, INF);
      dist[start] = 0;

      PriorityQueue<Route> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
      pq.offer(new Route(start,1,0,null));

      Route now;
      while (!pq.isEmpty()) {
         now = pq.poll();
         if (visited[now.city]) continue;
         visited[now.city] = true;
         dist[now.city] = now.cost;

         if(now.city==end){
            return getResult(now);
         }

         for (Node node = edges[now.city]; node != null; node = node.next) {
            if (dist[node.to] <= node.cost + now.cost) continue;
            dist[node.to] = node.cost + now.cost;
            pq.offer(new Route(node.to,now.count+1, dist[node.to], now));
         }
      }

      return "";
   }

   private static String getResult(Route now) {
      StringBuilder res = new StringBuilder();
      res.append(now.cost).append('\n');
      res.append(now.count).append('\n');

      int[] tmp = new int[now.count];
      for(int i=tmp.length-1;i>=0;i--){
         tmp[i] = now.city;
         now = now.next;
      }

      for (int j : tmp) res.append(j).append(' ');

      return res.toString();
   }

   private static class Node {
      int to, cost;
      Node next;

      Node(int to, int cost, Node next) {
         this.to = to;
         this.cost = cost;
         this.next = next;
      }
   }

   private static class Route {
      int count, city, cost;
      Route next;
      Route(int city, int count, int cost, Route next){
         this.city = city;
         this.count = count;
         this.cost = cost;
         this.next = next;
      }
   }
}

---

3. 결과

tmp를 사용하지 않고 arraylist를 사용해봤는데 거기서 거기였다.