1504번 - 특정한 최단 경로

1️⃣ Dijkstra Algorithm

 

✏️ 풀이 과정

풀이 방법에 대한 발상 자체는 해볼만 하지만 과정이 굉장히 길어지기 때문에 시도하기가 어려웠던 문제였습니다. 1에서 N으로 갈 때 v1과 v2를 모두 거쳐 N으로 가는 최단경로를 계산하는 문제인데 정점이 800개이고 간선이 200000개까지 가능하기 때문에 모든 경로를 탐색해서 최단경로를 찾는 것은 시간 상 어렵습니다. (가지치기를 시행해서 어느정도 줄어드나 O(2^N)까지 가능합니다.

 

문제에서 반드시 최단경로로 이동한다는 사실에 주의하라는 힌트를 고려하면 새로운 방법을 생각할 수 있습니다. 바로 1, v1, v2, N 사이에서만 서로 간의 최단거리를 구해서 정점이 4개인 새로운 그래프를 만들어 이 축소된 그래프에서 모든 가능한 경로를 탐색하는 것입니다. 이 경우 1이 출발점이기 때문에 가능한 경로는 3*2*1 = 6가지 뿐입니다.(첫 방문 * 두 번째 방문 * 세 번째 방문)

 

문제를 축소하면 빠른 시간 내에 해결할 수 있다는 것을 알았기 때문에 가장 중요한 것은 각 정점 간의 최단거리를 구하는 것이 됩니다. 제가 배운 과정 내에서는 한 정점으로부터 다른 정점까지의 최단거리를 구하는 알고리즘은 다익스트라 알고리즘 뿐입니다.(벨만-포드 알고리즘도 있긴 한데 음수 가중치가 존재하는 경우에 사용되고 다익스트라와 정확히 같은 일을 합니다.)  여기서 정점이 800개까지 있는데 대략 3+2+1 = 6개의 최단거리를 구하기 위해서 다익스트라 알고리즘을 3번이나 사용한다는 점이 걸려서 이 풀이에 접근하는 데 오랜 시간이 걸렸는데 시간 복잡도를 계산해보면 다익스트라 알고리즘의 경우 O((V+E)logV)이므로 한 번 실행마다 대략 200800*2(대략 한자리수) 정도로 1억 번에 한참 못미치기 때문에 3번 실행해도 시간 상 문제가 없습니다.

 

그렇기 때문에 1과 v1, v2에 대해 각각 다익스트라 알고리즘을 실행해서 모든 다른 정점에 대한 최단거리를 구하고 1 - v1, v2, N / v1 - v2, N / v2 - N 간의 거리를 이용해서(양방향으로 연결하기 때문에 N에는 시행하지 않아도 됩니다. 연결된 모든정점에 대한 거리가 이미 계산되었기 때문에) 정점이 4개인 새로운 그래프를 만들었습니다. 이후 dfs를 이용해서 이 그래프에서 가능한 모든 경로를 탐색하며 그 중 v1과 v2를 먼저 방문하고 N에 도착한 경우에 최단거리 값을 업데이트해서 전체적인 최단 거리를 구할 수 있었습니다.

 

이 과정에서 주의할 점은 다익스트라 알고리즘을 이용할 때 연결되지 않은 정점 사이의 거리를 무한대로 표기해야 하는데 Integer.MAX_VALUE같은 것을 사용하면 오버플로우가 발생하기 때문에 더할 수 있는 최댓값을 더해도 오버플로우가 나지 않는 적절한 값으로 바꿔야 합니다. 그리고 마지막에 dfs를 돌릴 때도 거리가 무한대인 경우를 고려하는 것을 방지하기 위해 가중치가 이 설정한 값에 해당할 경우 continue를 이용해서 건너뛰어야 합니다.  

 

⏱ 시간 복잡도

문제 해결은 전체적으로 3번의 다익스트라 알고리즘과 1번의 dfs 시행으로 이루어져 있습니다. 전자의 경우 O((V+E)logV)이고 후자의 경우 정점의 개수가 적어 for문이 3^3=27번 안쪽으로 실행되기 때문에 상수에 가깝습니다. 그래서 전체적인 시간 복잡도는 다익스트라 알고리즘에 사용된 O((V+E)logV)이 됩니다. V가 최대 800이고 E가 200000까지임을 고려할 때 시간적으로 충분히 3초 내에 해결이 가능한 것을 예측할 수 있습니다. 

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	// N과 v1, v2의 번호
	static int N, v1, v2;
	// 인접 리스트로 그래프 구현
	static Node[] adjList;
	// 거리의 최솟값
	static int min;
	
	// 인접 리스트 구현을 위한 정점 클래스
	static class Node implements Comparable<Node> {
		int v;
		int dist;
		Node link;
		
		public Node(int v, int dist, Node link) {
			this.v = v;
			this.dist = dist;
			this.link = link;
		}
		
		// 다익스트라 알고리즘을 구현할 때 우선순위 큐를 사용하기 위해 구현
		@Override
		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
	}
	
	// 다익스트라 알고리즘, 결과를 dist 배열에 저장
	static void shortest_path(int v, int[] dist) {
		// 인접 리스트 및 우선순위 큐 이용
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.offer(new Node(v, 0, null));
		Node cur;
		dist[v] = 0;
		while(!q.isEmpty()) {
			cur = q.poll();
			if(cur.dist > dist[cur.v]) {
				continue;
			}
			for(Node n=adjList[cur.v];n!=null;n=n.link) {
				if(dist[n.v] > dist[cur.v] + n.dist) {
					dist[n.v] = dist[cur.v] + n.dist;
					q.offer(n);
				}
			}
		}
	}
	
	// 정점 4개인 그래프로 변경해서 DFS를 통해 모든 순서를 고려해서 최단거리 계산
	static void dfs(int v, int sum, boolean[] visited) {
		if(sum > min) {
			return;
		}
		// v1과 v2를 방문한 적이 있을 때만 업데이트
		if(v == 3 && visited[1] && visited[2]) {
			min = sum;
		}
		for(Node n=adjList[v];n!=null;n=n.link) {
			// 길이 없는 경우 건너뜀
			if(n.dist == Integer.MAX_VALUE - 1000) {
				continue;
			}
			if(!visited[n.v]) {
				visited[n.v] = true;
				dfs(n.v, sum+n.dist, visited);
				visited[n.v] = false;
			}
		}
	}
	
	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());
		int E = Integer.parseInt(st.nextToken());
		int from, to, dist;
		adjList = new Node[N+1];
		// 입력을 받아 인접 리스트로 저장
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			dist = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, dist, adjList[from]);
			adjList[to] = new Node(from, dist, adjList[to]);
		}
		st = new StringTokenizer(br.readLine());
		v1 = Integer.parseInt(st.nextToken());
		v2 = Integer.parseInt(st.nextToken());
		min = Integer.MAX_VALUE;
		// 1, v1, v2에 대해 다익스트라 알고리즘 실행
		int[] dist1 = new int[N+1];
		int[] distv1 = new int[N+1];
		int[] distv2 = new int[N+1];
		Arrays.fill(dist1, Integer.MAX_VALUE-1000);
		Arrays.fill(distv1, Integer.MAX_VALUE-1000);
		Arrays.fill(distv2, Integer.MAX_VALUE-1000);
		shortest_path(1, dist1);
		shortest_path(v1, distv1);
		shortest_path(v2, distv2);
		
		// 1, v1, v2, N만 존재하는 새로운 인접 리스트 생성
		adjList = new Node[4];
		boolean[] visited = new boolean[4];
		
		adjList[0] = new Node(1, dist1[v1], adjList[0]);
		adjList[1] = new Node(0, dist1[v1], adjList[1]);
		adjList[0] = new Node(2, dist1[v2], adjList[0]);
		adjList[2] = new Node(0, dist1[v2], adjList[2]);
		adjList[0] = new Node(3, dist1[N], adjList[0]);
		adjList[3] = new Node(0, dist1[N], adjList[3]);
		
		adjList[1] = new Node(2, distv1[v2], adjList[1]);
		adjList[2] = new Node(1, distv1[v2], adjList[2]);
		adjList[1] = new Node(3, distv1[N], adjList[1]);
		adjList[3] = new Node(1, distv1[N], adjList[3]);
		
		adjList[2] = new Node(3, distv2[N], adjList[2]);
		adjList[3] = new Node(2, distv2[N], adjList[3]);
		
		// 새로운 인접 리스트에서 dfs를 통해 최단거리를 계산
		dfs(0, 0, visited);
		// 최단거리가 업데이트되지 않은 경우 -1를 출력, 이외에는 최단거리를 출력
		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
		br.close();
	}
}