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

문제

https://www.acmicpc.net/problem/1504

풀이

• 무방향 그래프
• 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다.
• 임의로 주어진 두 정점은 반드시 통과해야 한다.
• 한 번 이동했던 정점은 물론, 간선도 다시 이동할 수 있다.
• 하지만, "반드시" 최단 경로로 이동해야 한다.

다익스트라(Dijkstra) 문제입니다.

문제를 잘 보시면 그냥 최단 경로를 찾는 것이 아닌, 두 정점을 반드시 지나는 최단 경로를 찾는 문제입니다.

1번 정점에서 시작해 임의의 두 정점을 지나고 N번 정점을 지나야 하므로 우리는 2가지 방식으로 최단 경로를 구할 수 있습니다.

1. 1번 정점 -> 임의의 정점 1 -> 임의의 정점 2 -> N번 정점
2. 1번 정점 -> 임의의 정점 2 -> 임의의 정점 1 -> N번 정점

이 점을 이용해 문제를 풀어보겠습니다.

---

특정 정점까지의 거리를 관리하기 위해 클래스를 생성하겠습니다.

	static class Node implements Comparable<Node> {
		int idx, cost; // 정점 번호, 가중치(거리)
		
		Node (int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost; // 가중치 오름차순 정렬
		}
	}

• 최소힙 순서를 가중치 순으로 정렬하기 위해 compareTo를 오버라이딩 해줍니다.

		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
		
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
            // 무방향(양방향)
			graph.get(a).add(new Node(b, c));
			graph.get(b).add(new Node(a, c));
		}

• 인접 리스트로 구현했습니다.
• 무방향 그래프이므로 (a -> b) 뿐만 저장하는 것이 아닌 (b -> a)도 저장해야 합니다.

---

	// 다익스트라 메서드
	private static int[] dijkstra(int start) {
    	// 리턴할 거리 정보
		dist = new int[n+1];
		Arrays.fill(dist, INF);
		dist[start] = 0;

• 다익스트라 메서드입니다.
• 거리는 최소 거리를 저장해야 하므로 시작 지점을 제외한 나머지 부분을 최댓값인 INF로 초기화했습니다.

        // 최소 힙
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0)); // 이동한 노드(시작 지점), 이동한 거리(0)
		
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			
			int u = cur.idx; // 현재 노드
			int d = cur.cost; // 현재까지 이동 거리
			
			if (dist[u] < d) continue; // 현재 노드의 이동거리가 이미 최소라면 continue

• pq에 현재 노드의 정보와 이동한 거리를 넣어 줍니다.
• 현재 방문한 노드의 이동거리가 이미 최소라면 conitnue를 해주어야 합니다.(아니라면 시간 초과 발생)

            // 다음 노드 탐색
			for (Node nxt : graph.get(u)) {
				int v = nxt.idx; // 다음 노드
				int w = nxt.cost; // 다음 노드까지의 거리
				
                // 현재 저장된 다음 노드까지의 거리보다
                // 현재 노드에서 다음 노드까지의 거리가 더 짧다면
				if (dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w; // 최솟값 갱신
					pq.add(new Node(v, dist[v])); // 다음 노드, 다음 노드까지의 거리 삽입
				}
			}
		}
		
		return dist;
	}

• 현재 노드를 꺼내왔으면, 인접한 노드들을 탐색합니다.
• dist에 저장된 다음 노드의 거리가 "현재 노드 -> 다음 노드" 거리가 더 짧다면, 값을 업데이트해 줍니다.

---

위에 설명했듯이, 우리는 임의의 두 노드를 지나는 2가지 경로를 고려할 수 있습니다.

1. 1 -> v1 -> v2 -> n
2. 1 -> v2 -> v1 -> n

그러기 위해선 각각의 노드에서 최소 경로를 탐색해야 합니다.

ex) 1 -> v1 -> v2 -> n

• (1 -> v1) 최소 경로
• (v1 -> v2) 최소 경로
• (v2 -> n) 최소 경로

		int[] from1 = dijkstra(1);
		int[] fromV1 = dijkstra(v1);
		int[] fromV2 = dijkstra(v2);

3개의 시작 지점을 구했으니 각각의 도착 지점을 설정해 값을 구하면 됩니다.

		int path1, path2;
        
		// 1. 1 -> v1 -> v2 -> n
		if (from1[v1] == INF || fromV1[v2] == INF || fromV2[n] == INF) path1 = INF;
		else path1 = from1[v1] + fromV1[v2] + fromV2[n];

		// 2. 1 -> v2 -> v1 -> n
		if (from1[v2] == INF || fromV2[v1] == INF || fromV1[n] == INF) path2 = INF;
		else path2 = from1[v2] + fromV2[v1] + fromV1[n];

• 경로가 없다면 INF로 초기화 했습니다.

		int answer = Math.min(path1, path2);
		System.out.println(answer == INF ? -1 : answer);

• 두 경로 중 최솟값을 출력하면 끝입니다.
• 만약 경로가 없다면(INF) -1을 출력

코드

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

public class Main {
	
	static class Node implements Comparable<Node> {
		int idx, cost;
		
		Node (int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}
	
	static final int INF = (int) 1e9;
	static int n, e, v1, v2;
	static int[] dist;
	static List<ArrayList<Node>> graph;

	private static int[] dijkstra(int start) {
		dist = new int[n+1];
		Arrays.fill(dist, INF);
		dist[start] = 0;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			
			int u = cur.idx;
			int d = cur.cost;
			
			if (dist[u] < d) continue;
			
			for (Node nxt : graph.get(u)) {
				int v = nxt.idx;
				int w = nxt.cost;
				
				if (dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w;
					pq.add(new Node(v, dist[v]));
				}
			}
		}
		
		return dist;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
		
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			graph.get(a).add(new Node(b, c));
			graph.get(b).add(new Node(a, c));
		}
		
		st = new StringTokenizer(br.readLine());
		v1 = Integer.parseInt(st.nextToken());
		v2 = Integer.parseInt(st.nextToken());
		
		int[] from1 = dijkstra(1);
		int[] fromV1 = dijkstra(v1);
		int[] fromV2 = dijkstra(v2);
		
		int path1, path2;
		
		// 1. 1 -> v1 -> v2 -> n
		if (from1[v1] == INF || fromV1[v2] == INF || fromV2[n] == INF) path1 = INF;
		else path1 = from1[v1] + fromV1[v2] + fromV2[n];

		// 2. 1 -> v2 -> v1 -> n
		if (from1[v2] == INF || fromV2[v1] == INF || fromV1[n] == INF) path2 = INF;
		else path2 = from1[v2] + fromV2[v1] + fromV1[n];
		
		int answer = Math.min(path1, path2);
		System.out.println(answer == INF ? -1 : answer);
	}

}