[BOJ] 5972 택배 배송 - JAVA

1. 문제

5972번: 택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

---

2. 풀이

Node 클래스

현재 Node 객체에서 도착하는 지점(to), 소의 마리 수(cow), 같은 길에서 출발하는 다른 길들을 next에 저장한다.

private static class Node {
   int to, cow;
   Node next;
   Node(int to, int cow, Node next){
      this.to = to;
      this.cow = cow;
      this.next = next;
   }
}

 

Main

양방향 그래프이기 때문에 Node타입 배열 road에 a->b, b->a로 두 번 저장한다. 

다익스트라 탐색 결과를 바로 출력하고 끝낸다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   int N = Integer.parseInt(st.nextToken());
   int M = Integer.parseInt(st.nextToken());

   Node[] road = new Node[N+1];
   int a, b, c;
   for(int m=0;m<M;m++){
      st = new StringTokenizer(in.readLine());
      a = Integer.parseInt(st.nextToken());
      b = Integer.parseInt(st.nextToken());
      c = Integer.parseInt(st.nextToken());

      road[a] = new Node(b,c,road[a]);
      road[b] = new Node(a,c,road[b]);
   }

   System.out.println(dijkstra(N,road));
}

 

Dijkstra

int[] 타입을 받는 PriorityQueue를 사용한다. 0번째 칸에는 헛간 번호, 1번째 칸에는 그 헛간까지 도달할 때까지 만나는 소의 마리수를 저장한다. 소의 마리 수 대로 오름차순 정렬하도록 한다.

1번째 헛간부터 시작하도록 pq에 시작지점을 넣는다.

 

pq가 빌 때까지 탐색한다.

1. 이미 방문한 헛간(소를 최소로 만남)은 다시 방문하지 않는다.

2. count에는 1부터 헛간을 방문할 때까지 만나는 소의 마리수를 저장한다.

3. road[now[0]]부터 하나씩 next로 옮겨가면서 now[0]에서 이동할 수 있는 모든 헛간을 탐색한다. 이때, count[다음헛간]이 count[현재헛간]+다음헛간까지 가는 길의 소 수(r.cow)보다 클 때만 다시 pq에 넣는다.

 

count[N]을 반환한다. 

private static int dijkstra(int N, Node[] road){
   boolean[] visited = new boolean[N+1];
   int[] count = new int[N+1];
   Arrays.fill(count,50_000_001);
   PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
   pq.offer(new int[]{1,0});

   int[] now;
   while(!pq.isEmpty()){
      now = pq.poll();
      if(visited[now[0]]) continue;
      visited[now[0]] = true;
      count[now[0]] = now[1];

      for(Node r=road[now[0]];r!=null;r = r.next){
         if(count[r.to] > now[1] + r.cow){
            count[r.to] = now[1] + r.cow;
            pq.offer(new int[]{r.to, count[r.to]});
         }
      }
   }

   return count[N];
}

 

전체 코드

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

public class BOJ_5972_택배배송 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      Node[] road = new Node[N+1];
      int a, b, c;
      for(int m=0;m<M;m++){
         st = new StringTokenizer(in.readLine());
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         c = Integer.parseInt(st.nextToken());

         road[a] = new Node(b,c,road[a]);
         road[b] = new Node(a,c,road[b]);
      }

      System.out.println(dijkstra(N,road));
   }

   private static int dijkstra(int N, Node[] road){
      boolean[] visited = new boolean[N+1];
      int[] count = new int[N+1];
      Arrays.fill(count,50_000_001);
      PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
      pq.offer(new int[]{1,0});

      int[] now;
      while(!pq.isEmpty()){
         now = pq.poll();
         if(visited[now[0]]) continue;
         visited[now[0]] = true;
         count[now[0]] = now[1];

         for(Node r=road[now[0]];r!=null;r = r.next){
            if(count[r.to] > now[1] + r.cow){
               count[r.to] = now[1] + r.cow;
               pq.offer(new int[]{r.to, count[r.to]});
            }
         }
      }

      return count[N];
   }

   private static class Node {
      int to, cow;
      Node next;
      Node(int to, int cow, Node next){
         this.to = to;
         this.cow = cow;
         this.next = next;
      }
   }
}

---

3. 결과