[백준 / Java] 1504번 : 특정한 최단 경로

문제

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

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1 복사

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 복사

7

---

문제 풀이

 해당 문제는 양방향의 길을 통해 최단 거리를 구하는 문제이다. 추가적으로 1번째 점에서 N번째 점으로 도달하는 과정에서 2개의 점을 무조건 경유해서 도착해야 한다는 조건을 가진다.

 

 조건을 보면 까다로워 보일 수 있으나 두 점을 경유하며 지정한 위치로 최단 거리로 가는 경우의 수를 생각하면 쉽게 구할 수 있다.

 

 두 점을 경유하며 목적지로 가는 방법은 두가지 뿐이다.

1. 출발지 -> 목적지 1 -> 목적지 2 -> 도착지

2. 출발지 -> 목적지 2 -> 목적지 1 -> 도착지

 

 위 과정에서 각 점과 점 사이의 거리는 다익스트라(테이크스트라) 알고리즘을 사용하면 쉽게 구할 수 있다. 다익스트라 알고리즘에 대한 자세한 설명은 아래 포스팅을 확인하면 이해하기 좋을 것 같다.

2023.07.22 - [algorithm/theory] - 다익스트라(Dijkstra) 알고리즘

 

 출발지에서 모든 점까지의 최단거리, 목적지 1에서 모든 점까지의 최단거리, 목적지 2에서 모든 점까지의 최단거리 총 3번의 다익스트라 알고리즘을 사용하여 구하고, 위 두가지 방법 중 짧은 거리를 출력하면 정답으로 나온다.

 

 이 때 만약 도달할 수 없다면(최단 거리가 INF보다 높을 경우, INF는 무한) -1을 출력하는 예외 처리를 해주어야 한다.

---

코드 풀이

 문제를 풀면서 각 점까지의 거리의 최소를 쉽게 구하기 위해 Point class를 구현하여 사용하였다.

public static class Point implements Comparable<Point>{
		int index;
		int distance;
		
		public Point(int index, int distace) {
			this.index = index;
			this.distance = distace;
		}
        
		@Override
		public int compareTo(Point o) {
			return this.distance - o.distance;
		}
	}

 구현을 하며 우선순위 큐(PriorityQueue)에서 거리의 최소를 구하기 위해 compareTo를 구현하여 거리가 작은 순으로 배열할 수 있도록 했다.

 

 

 다음으로는 원하는 점에서 최단 거리를 구하는 Dijkstra 메서드를 구현하였다.

public static int[] dijkstra(int start) {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N+1];
		int[] dp = new int[N+1];
		Arrays.fill(dp, INF);
		
		pq.add(new Point(start, 0));
		dp[start] = 0;
		
		while(!pq.isEmpty()) {
			Point pos = pq.poll();
			
			int to = pos.index;
			
			if(visited[to]) continue;
			
			visited[to] = true;
			
			for(Point next : route.get(to)) {
				if(dp[to] + next.distance < dp[next.index]) {
					dp[next.index] = dp[to] + next.distance;
					pq.add(new Point(next.index, dp[next.index]));
				}
			}
		}
		
		return dp;
	}

 

정답 코드는 아래와 같다.

import java.io.*;
import java.util.*;
 
public class Main {
 
	public static class Point implements Comparable<Point>{
		
		int index;
		int distance;
		
		public Point(int index, int distace) {
			this.index = index;
			this.distance = distace;
		}
		@Override
		public int compareTo(Point o) {
			return this.distance - o.distance;
		}
	}
	
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int INF = 100_000_000;
	
	public static int N;
	public static int E;
	
	public static ArrayList<ArrayList<Point>> route;
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken()); 
		E = Integer.parseInt(st.nextToken());
		
		int point1 = 0;
		int point2 = 0;
		
		route = new ArrayList<ArrayList<Point>>();
		
		for(int i = 0 ; i <= N; i++) {
			route.add(new ArrayList<>());
		}
		
		
		for(int i = 0; i < E; i++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine()," ");
			
			point1 = Integer.parseInt(st1.nextToken());
			point2 = Integer.parseInt(st1.nextToken());
			int distance = Integer.parseInt(st1.nextToken());
			
			route.get(point1).add(new Point(point2,distance));
			route.get(point2).add(new Point(point1,distance));
		}
		
		StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
		int target1 = Integer.parseInt(st2.nextToken());
		int target2 = Integer.parseInt(st2.nextToken());
		
		
		int[] startAtS = dijkstra(1);
		int[] startAt1 = dijkstra(target1);
		int[] startAt2 = dijkstra(target2);
	
		
		int sum1 = startAtS[target1] + startAt1[target2] + startAt2[N];
		int sum2 = startAtS[target2] + startAt2[target1] + startAt1[N];
		
		int min = Math.min(sum1, sum2);
		
		if(min >= INF)
			System.out.println("-1");
		else
			System.out.println(min);
	}
	
	public static int[] dijkstra(int start) {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N+1];
		int[] dp = new int[N+1];
		Arrays.fill(dp, INF);
		
		pq.add(new Point(start, 0));
		dp[start] = 0;
		
		while(!pq.isEmpty()) {
			Point pos = pq.poll();
			
			int to = pos.index;
			
			if(visited[to]) continue;
			
			visited[to] = true;
			
			for(Point next : route.get(to)) {
				if(dp[to] + next.distance < dp[next.index]) {
					dp[next.index] = dp[to] + next.distance;
					pq.add(new Point(next.index, dp[next.index]));
				}
			}
		}
		
		return dp;
	}
	
}