[BOJ] 1504 특정한 최단 경로 - JAVA

1. 문제

1504번: 특정한 최단 경로

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

---

2. 풀이

Node 클래스

도착지, 거리, 다음 노드 주소값을 저장하는 클래스를 만든다.

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

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

 

static 변수

int N	정점의 개수
int INF = 200_000_001	간선 최대 개수 * 최대 거리 + 1 한 값
Node[] edges	간선 배열.

 

Dijkstra

N개의 정점과 E개의 간선을 이용해 start부터 end까지 어느 정도의 거리가 걸리는지 탐색하고, 그 거리를 반환한다.

일반적인 다익스트라 풀이와 똑같다.

private static int dijkstra(int start, int end) {
   int[] dist = new int[N + 1];
   boolean[] visited = new boolean[N + 1];
   Arrays.fill(dist, INF);
   dist[start] = 0;
   PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
   pq.offer(new int[]{start, 0});

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

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

   return dist[end];
}

 

Main

정점 수, 간선 수, 간선들 정보를 모두 입력받는다.

양방향 간선이기 때문에 edges[from]과 edges[to] 모두에 간선 정보를 저장한다.

1부터 N까지 가려고 할 때 V1, V2를 모두 들리려면 두 가지 방법밖에 없다.

1) 1 → v1 → v2 → N

2) 1 → v2 → v1 → N

따라서 이 두 가지 값을 구한다. 각 경우마다 세 번의 다익스트라 탐색을 해야한다.(화살표 부분)

두 경우 중 최솟값을 출력하되, 최솟값이 앞에서 정한 INF값보다 크거나 같다면 -1을 출력한다.(경로 없는 경우)

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

   edges = new Node[N + 1];
   int from, to, distance;
   for (int i = 0; i < E; i++) {
      st = new StringTokenizer(in.readLine());
      from = Integer.parseInt(st.nextToken());
      to = Integer.parseInt(st.nextToken());
      distance = Integer.parseInt(st.nextToken());
      edges[from] = new Node(to, distance, edges[from]);
      edges[to] = new Node(from, distance, edges[to]);
   }

   st = new StringTokenizer(in.readLine());
   int V1 = Integer.parseInt(st.nextToken());
   int V2 = Integer.parseInt(st.nextToken());

   int case1 = dijkstra(1, V1) + dijkstra(V1, V2) + dijkstra(V2, N);
   int case2 = dijkstra(1, V2) + dijkstra(V2, V1) + dijkstra(V1, N);

   int result = Math.min(case1, case2);
   if(result >= INF) System.out.println(-1);
   else System.out.println(result);
}

 

전체 코드

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

public class BOJ_1504_특정한최단경로 {
   static int N;
   static int INF = 200_000_001;
   static Node[] edges;
   
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      int E = Integer.parseInt(st.nextToken());

      edges = new Node[N + 1];
      int from, to, distance;
      for (int i = 0; i < E; i++) {
         st = new StringTokenizer(in.readLine());
         from = Integer.parseInt(st.nextToken());
         to = Integer.parseInt(st.nextToken());
         distance = Integer.parseInt(st.nextToken());
         edges[from] = new Node(to, distance, edges[from]);
         edges[to] = new Node(from, distance, edges[to]);
      }

      st = new StringTokenizer(in.readLine());
      int V1 = Integer.parseInt(st.nextToken());
      int V2 = Integer.parseInt(st.nextToken());

      int case1 = dijkstra(1, V1) + dijkstra(V1, V2) + dijkstra(V2, N);
      int case2 = dijkstra(1, V2) + dijkstra(V2, V1) + dijkstra(V1, N);

      int result = Math.min(case1, case2);
      if(result >= INF) System.out.println(-1);
      else System.out.println(result);
   }

   private static int dijkstra(int start, int end) {
      int[] dist = new int[N + 1];
      boolean[] visited = new boolean[N + 1];
      Arrays.fill(dist, INF);
      dist[start] = 0;
      PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
      pq.offer(new int[]{start, 0});

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

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

      return dist[end];
   }

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

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

---

3. 결과