[백준] 1753. 최단경로 (JAVA)

🚙 최단경로

 

다익스트라(Dijkstra) 알고리즘은 그래프의 한 지점으로부터 모든 지점까지의 최단 경로를 구하는 알고리즘이다. 이 문제는 전형적인 다익스트라 알고리즘 문제의 예시라고 할 수 있으며, Dynamic Programming을 이용하여 구현할 수 있다. 

 

---

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

---

💡  나의 풀이

1번 풀이: 선형탐색 - 시간복잡도 O(V²)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Edge {
	int dest;
	int weight;

	Edge(int dest, int weight) {
		this.dest = dest;
		this.weight = weight;
	}
}

class Main {
	static int V;
	static int E;
	static int start;
	static int[] distance;
	static boolean[] visited;
	static List<Edge>[] connected;
	static final int INF = 10000000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		distance = new int[V+1];
		visited = new boolean[V+1];
		connected = new ArrayList[V+1];

		Arrays.fill(distance, INF);
		distance[start] = 0;

		for(int i=1; i<V+1; i++) {
			connected[i] = new ArrayList<>();
		}

		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 weight = Integer.parseInt(st.nextToken());
			connected[from].add(new Edge(to, weight));
		}

		dijkstra();

		for(int i=1; i<V+1; i++) {
			if (distance[i] == INF)
				System.out.println("INF");
			else System.out.println(distance[i]);
		}
	}

	private static void dijkstra() {
		for(int i=0; i<V; i++) {
			int next = closestIndex();
			visited[next] = true;
			for(Edge edge: connected[next]) {
				int v = edge.dest;
				int w = edge.weight;
				distance[v] = Math.min(distance[v], distance[next] + w);
			}
		}
	}

	private static int closestIndex() {
		int min = INF;
		int minIdx = -1;

		for(int i=1; i<V+1; i++) {
			if(visited[i]) continue;
			if(distance[i] <= min) {
				min = distance[i];
				minIdx = i;
			}
		}
		return minIdx;
	}
}

 

인접리스트를 이용하여 구현하였다.

 

인접행렬을 이용하여 구현할 경우, 정점의 개수가 최대 20,000이기 때문에

4B * 20,000 * 20,000 = 16 * 10^8 B = 1600MB 로, 메모리 제한 256MB를 훨씬 초과한다. 

 

또한 정점의 개수에 비해 간선이 적을 때는 인접리스트를 사용하는 것이 압도적으로 유리하다. 

 

위의 풀이에서는 매번 closestIndex() 를 이용해 반복문을 돌며 방문하지 않은 정점 중 distance가 가장 작은 인덱스를 찾는다.

이와 같이 선형탐색을 이용하는 경우 시간 복잡도가 O(V²)가 된다.

 

정점의 수가 적거나 간선의 수가 매우 많은 경우에는 위와 같은 방법을 사용하는 것이 훨씬 빠르겠지만,

현재 주어진 정점 개수는 최대 2만개이므로 위의 방법은 굉장히 비효율적이다. 

 

그러나 Heap 자료구조로 구현된 Java의 PriorityQueue를 활용하면 시간 복잡도를 O(E*logV) 까지 줄일 수 있다.

 

2번 풀이: 우선순위 큐(Priority Queue) - 시간복잡도 O(E*logV)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Edge implements Comparable<Edge> {
	int vertex;
	int weight;

	Edge(int vertex, int weight) {
		this.vertex = vertex;
		this.weight = weight;
	}

	@Override
	public int compareTo(Edge e) {
		return this.weight - e.weight;
	}
}

class Main {
	static int V;
	static int E;
	static int start;
	static int[] distance;
	static boolean[] visited;
	static List<Edge>[] connected;
	static final int INF = 10000000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		distance = new int[V+1];
		visited = new boolean[V+1];
		connected = new ArrayList[V+1];

		Arrays.fill(distance, INF);
		distance[start] = 0;

		for(int i=1; i<V+1; i++) {
			connected[i] = new ArrayList<>();
		}

		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 weight = Integer.parseInt(st.nextToken());
			connected[from].add(new Edge(to, weight));
		}

		dijkstra();

		for(int i=1; i<V+1; i++) {
			if (distance[i] == INF)
				System.out.println("INF");
			else System.out.println(distance[i]);
		}
	}

	private static void dijkstra() {
		PriorityQueue<Edge> queue = new PriorityQueue<>();
		queue.offer(new Edge(start, distance[start]));

		while(!queue.isEmpty()) {
			Edge closest = queue.poll();

			if(visited[closest.vertex]) continue;
			visited[closest.vertex] = true;

			for(Edge dest: connected[closest.vertex]) {
				if(distance[dest.vertex] > distance[closest.vertex] + dest.weight) {
					distance[dest.vertex] = distance[closest.vertex] + dest.weight;
					queue.offer(new Edge(dest.vertex, distance[dest.vertex]));
				}
			}
		}
	}
}

 

정리하자면,

다익스트라 알고리즘을 구현하는데는

 

1. 선형탐색과
2. 우선순위 큐 방식

두 가지가 있는데

무조건적으로 둘 중 어떤 것이 더 성능이 좋다고 할 수는 없으며

두 방식의 시간복잡도를 고려하여 문제 상황에 따라 선택할 수 있어야 한다.  

 

 

---

 

1753번: 최단경로