/
/

BOJ : 백준 1504 특정한 최단 경로

백준 1504 특정한 최단 경로 풀이 기록 💡
알고리즘그래프
avatar
vari
2025.04.30
·
6 min read

문제

문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력
정점의 개수 N 간선의 개수 E (2<=N<=800, 0<=E<=200,000)
E개의 줄을 걸쳐 a정점 b정점 c거리
이후 반드시 거쳐야 하는 v1, v2
v1과 v2는 무조건 다르고 u, v 사이에는 간선이 최대 1개 존재

출력
두 정점을 지나는 최단 경로의 길이를 출력
없으면 -1

풀이

최단 경로를 찾아야하므로 다익스트라를 사용
처음에는 다익스트라 함수 내부에 result 배열을 따로 생성해서 u, v를 방문한 경우 따로 갱신을 하려고 했다. 근데... visited 배열을 통해 검증하는 것은 전체 탐색 과정에서 두 정점을 방문했는지를 검증할 수 있는 거고 현재 탐색에서 방문했는지는 알 수 없는 검증 방식이었다...

가능한 경로는 두 가지 방법이다.
1 → u → v → N
1 → v → u → N

이걸 보고 아니 왜?! 1 → 2 → u → 3 → v → N일 수도 있잖아 라는 생각을 잠깐 했었는데
다익스트라를 통해서 1을 돌려, u의 값을 구하면 뭘 거쳤든 간에 끝에 u로 도착하는 최단거리를 구해온다. 그러므로 1 → u라고 쓰여있어도 사실은 1 → (2 → 3 → 4 →) u일 수도 있는 것.
그리고 이동했던 간선도 다시 이동해도 상관 없으므로 그냥 다익스트라를 세 번 돌려 두 경우의 수 중 최소값을 구하면 된다!

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

public class Main {
	static int N, E, V1, V2;
	static List<Route>[] graph;
	static boolean[] visited;
	
	static class Route implements Comparable<Route>{
		int to;
		int cost;
		
		Route(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Route o) {
			return this.cost - o.cost;
		}
	}
	
	static int[] solution(int start) {
		PriorityQueue<Route> pq = new PriorityQueue<>();
		Arrays.fill(visited, false);
		
		int[] dp = new int[N+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		pq.add(new Route(start, 0));
		dp[start] = 0;
		
		while(!pq.isEmpty()) {
			Route current = pq.poll();
			int to = current.to;
			
			if(visited[to]) {
				continue;
			}
			
			visited[to] = true;
			for(Route next : graph[to]) {
				if(dp[to] + next.cost < dp[next.to]) {
					dp[next.to] = dp[to] + next.cost;
					pq.add(new Route(next.to, dp[next.to]));
				}
			}
		}
		return dp;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		graph = new ArrayList[N+1];
		for(int i=0; i<=N; i++) {
			graph[i] = new ArrayList<Route>();
		}

		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			graph[from].add(new Route(to, cost));
			graph[to].add(new Route(from, cost));
		}
		
		st = new StringTokenizer(br.readLine());
		V1 = Integer.parseInt(st.nextToken());
		V2 = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N+1];
		
		int[] from1 = solution(1);
		int[] fromV1 = solution(V1);
		int[] fromV2 = solution(V2);
		
		long path1 = -1, path2 = -1;
		// 갈 수 있는 길이 없어 Integer.MAX_VALUE로 떴을 때의 처리
        if(from1[V1] != Integer.MAX_VALUE 
			&& fromV1[V2] != Integer.MAX_VALUE
			&& fromV2[N] != Integer.MAX_VALUE) {
			path1 = from1[V1] + fromV1[V2] + fromV2[N];
		}
		
		if(from1[V2] != Integer.MAX_VALUE 
			&& fromV2[V1] != Integer.MAX_VALUE
			&& fromV1[N] != Integer.MAX_VALUE) {
			path2 = from1[V2] + fromV2[V1] + fromV1[N];
		}
		
		bw.write(Math.min(path1, path2) + "\n");
		bw.flush();
		bw.close();
		br.close();

	}

}

문제를 풀며

다른 분들이 작성한 정답 코드를 보니, INTEGER.MAX_VALUE 대신 가능한 범위 내의 최댓값인 200_000_000를 쓴 코드가 많았다. INTEGER.MAX_VALUE는 정말 거기다 +1만 되어도 음수가 되기 때문에... 오버플로우 방지를 위해 범위 내의 최댓값을 계산해보고 그걸로 최댓값을 설정하는 연습이 필요할 것 같다.

- 컬렉션 아티클