섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (3) - 다익스트라

🔎다익스트라 알고리즘이란?

그래프 최단 거리 구하는 알고리즘
1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 
2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 
3. 플로이드-와샬(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 

⬛ 08-4. 다익스트라

🟦 다익스트라 (one - to - All)

• 다익스트라 알고리즘 : 그래프에서 최단 거리 구하는 알고리즘
• 특정 노드에서 다른 노드들 간의 최단 거리를 구하는 탐색 알고리즘
• 엣지가 모두 양수 (cf. 벨만-포드의 경우 엣지 음수도 가능)
• 시간 복잡도 : O(ElogV)

🟧 다익스트라 알고리즘의 핵심 이론

1) 인접 리스트로 그래프 표현

2) 최단 거리 D[] 배열 초기화 - Arrays.fill(D, Integer.MAX_VALUE);

3) 시작점 세팅

 PriorityQueue<Node> PQ = new PriorityQueue<>();

 D[s] = 0,

 pQ.add(new Node(s, 0));

4) while(!pQ.isEmpty()) 

현재 cur 노드 뽑아서 방문 전인 노드의 경우에 한해서  현재 cur의 인접 정점 nx 정점을 뽑는다. 다음 정점인 nx가 1) 방문 전이면서 && 2) distance[nx] > distance[cur] + nx_value; 일때         //최단 거리 세팅         distance[nx] = distance[cv] + nx_val;        //pQ에 담기        pQ.add(new Node(nx, distance[nx]);

5) 큐가 빈 상태일 때까지 반복하면 결과값이 나온다.

---

🟦 백준 1753번. 최단 경로 구하기

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

풀이 

package to_0703_4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/*최단 경로 다시 풀이 */
class Node implements Comparable<Node>{
	int v;
	int val;
	Node(int v, int val){
		this.v = v;
		this.val = val;
	}
	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}

public class Main_Re {
	//방문체크용
	static boolean visited[];
	//최단거리용
	static int[] distance;
	//그래프표현용
	static ArrayList<ArrayList<Node>> graph;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int V = kb.nextInt();
		int E = kb.nextInt();
		int S = kb.nextInt();
		//초기화
		graph = new ArrayList<>();
		for(int i = 0; i<=V; i++) {
			graph.add(new ArrayList<Node>());
		}
		visited = new boolean[V+1];
		distance = new int[V+1];
		
		//distance 초기화
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			int w= kb.nextInt();
			graph.get(a).add(new Node(b, w));
		}
		
		//시작점 초기화 
		//pQ 기본 오르마순 정렬 
		PriorityQueue<Node> pQ = new PriorityQueue<>();
		distance[S] = 0;//0으로 세팅
		pQ.add(new Node(S, 0));
		
		while(!pQ.isEmpty()) {
			//현재 정점
			Node cur = pQ.poll();
			int c_v = cur.v;
			int c_val = cur.val;
			if(!visited[c_v]) {
				visited[c_v] = true;
				for(Node nx : graph.get(c_v)) {
					int nx_v = nx.v;
					int nx_val = nx.val;
					if(!visited[nx_v] && distance[nx_v]> distance[c_v]+nx_val) {
						distance[nx_v] = distance[c_v]+nx_val;
						pQ.add(new Node(nx_v, distance[nx_v]));
					}
				}
			}
		}
		
		for(int i=1; i<=V; i++) {
			if(visited[i]) System.out.println(distance[i]);
			else System.out.println("INF");
		}	
	}
}

---

🟦 백준 1916번. 최소비용 구하기

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이

package to_0703_5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/* 최소비용 다시RE
 * */
class Node implements Comparable<Node>{
	int v;
	int val;
	Node(int v, int val){
		this.v = v;
		this.val = val;
	}
	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main_Re {
	static int distance[];
	static boolean visited[];
	static ArrayList<ArrayList<Node>> graph;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int V = kb.nextInt();
		int E = kb.nextInt();
		//초기화
		visited = new boolean[V+1];
		distance = new int[V+1];
		graph = new ArrayList<>();
		
		for(int i=0; i<=V; i++) {
			graph.add(new ArrayList<Node>());
		}
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int w = kb.nextInt();
			graph.get(a).add(new Node(b, w));
		}
		
		int st = kb.nextInt();
		int ed = kb.nextInt();
		
		//시작점 세팅
		PriorityQueue<Node> pQ = new PriorityQueue<>();
		distance[st] = 0;
		pQ.add(new Node(st, 0));
		
		while(!pQ.isEmpty()) {
			//현재
			Node cur = pQ.poll();
			int c_v = cur.v;
			int c_val = cur.val;
			if(!visited[c_v]) {
				visited[c_v] = true;
				for(Node nx : graph.get(c_v)) {
					int nx_v = nx.v;
					int nx_val = nx.val;
					if(!visited[nx_v] && distance[nx_v]> distance[c_v] + nx_val) {
						distance[nx_v] = distance[c_v]+nx_val;
						pQ.add(new Node(nx_v, distance[nx_v]));
					}
				}
			}
		}
		
		//끝 지점까지의 최단거리
		System.out.println(distance[ed]);
	}
}