[알고리즘] 다익스트라 개념정리~~~!, BOJ1753 적용

이전에 했던 크루스칼, 크림이 최소신장트리(모든 정점을 있는 간선들 중에 가장 비용이 적은 애들)를 찾는 알고리즘이었다면, 다익스트라는 하나의 정점에서 다른 정점으로 가는 길목들 중에 가장 비용이 적은 간선들을 고르는 것이다.

 

목적은 달라도 구현방식은 유사하다. (비슷한데 조금씩 달라서 더 헷갈리기도 한다..ㅎㅎ)

정점 정보로(=행렬로) 입력값이 들어온다면? 

무식하게 행렬로 하는게 더 간단할 때가 있는 법이다.

 

순서대로 체크포인트:

1. 입력이 정점들로 주어지니 일단 다 받는다.
2. 다익스트라는 출발 정점->도착 정점 문제임을 잊지말자.
3. int[] distance부터 논리가 시작된다! distance[2]은 출발정점 ->2번정점으로 오는 최소비용이다. 주의할 게, 어디어디를 몇번 거쳐서 어케 왔든간에 출발정점에서 2번 정점에 도착할 때의 최소비용을 의미한다. 
   boolean[] visited도 필수. 트리처럼 아래로 내려가는 카운트가 있는것도 아니므로, 왔던곳 또가고 그러는거 방지
4. distance배열 원소들을 다 무한으로 넣어준다. just like 최댓값구할때 max=0으로 놓는것처럼.
5. 젤 처음엔 distance[start]=0으로 해줘야 함. 시작하는 곳은 비용이 0이야.
6. 42번부터의 논리가 매우 핵심이다. 특히 distance[j] > distance[current]+adjMatrix[current][j] 의 의미를 잘 생각해보도록.(천천히 생각하면 당연한것임: 한방에 j가는것보다 current들렸다가 j가는게 더 비용이 적을때를 말함)
7. 이렇게 다시 29번라인으로 반복: distance[] 원소가 원래 무한이었는데 출발점부터 시작해서 가장 가까운(비용이 적은) 애들부터 하나씩 확정해서 원소값을 바꿔나가게 된다. 원소가 총 V개니까 V번 반복하면 distance[]는 다 채워진다.(물론 이어지지 않을땐 무한으로 그대로 남겠지)

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

public class DijkstraTest1 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(in.readLine());
		
		int[][] adjMatrix = new int[V][V];
		int start = 0;
		
		StringTokenizer st = null;
		for(int i=0; i<V; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<V; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] distance = new int[V]; //나한테 오는 최소비용. 어디어디 거쳤든간에 출발점->나한테 오는 최소비용.
		boolean[] visited = new boolean[V]; //최소비용 확정여부
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		
		for(int i=0; i<V; i++) {//총 정점만큼 반복하며 distance[]을 확정한다 생각하면됨.
			//단계1. 최소비용 확정안된 정점들 중 가장 작은 애 선택
			int min = Integer.MAX_VALUE, current = 0;
			for(int j=0; j<V; j++) {
				if(!visited[j] && min>distance[j]) {
					min = distance[j];
					current = j;
				}
			}
			
			visited[current] = true;
			
			//단계2: 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지 않은 다른 정점의 최소비용들 업뎃해줌
			for(int j=0; j<V; j++) {
				if(!visited[j] && adjMatrix[current][j]!=0 
						&& distance[j] > distance[current]+adjMatrix[current][j]) {
					
					distance[j] =  distance[current]+adjMatrix[current][j];
				}
			}
		}
		
		System.out.println(Arrays.toString(distance));
		
	}
}

 

 

입력테스트:

5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 8 6 5 0

output==> 8


6
0 3 5 0 0 0
0 0 2 6 0 0
0 1 0 4 6 0
0 0 0 0 2 3
3 0 0 0 0 6
0 0 0 0 0 0

output==> 12


10
0 4 6 0 0 0 0 0 0 0
0 0 0 9 8 0 0 0 0 0
0 3 0 0 2 3 0 0 0 0
0 0 0 0 0 0 6 0 0 0
0 0 0 2 0 1 3 7 0 0 
0 0 0 0 0 0 0 4 8 0
0 0 0 0 0 0 0 0 0 13
0 0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0

 

PriorityQueue, 인접리스트방식으로 효율적으로 받기

정점으로 행렬정보를 줄때는 물론 위의 방식처럼 mat[][] 만들어서 하면 됨. 여기에 위 코드 33번째줄에서 비용가장 작은정점 고를때 pq 써서 약간 빠르게 가능하긴 하지만, 크게 줄진 않는다. (관련코드는 생략. 어차피 곧 쓸 코드에 다 포함됨.)

보통 이런 최단거리 찾는 문제는 정점보다는 간선정보 형태로 많이 주어진다. (물론 정점정보 받아서 간선으로 바꾸는거 해도 괜찮긴 한데, 간선으로 바꿔야만 풀리는 문제는 걍 간선으로 주어짐). 간선으로 받은 정보를 인접리스트를 활용해서 풀면 훨씬 시간이 단축된다.

 

BOJ 1753을 풀면서 PQ랑 인접리스트 방식을 모두 적용해보자.

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

1753번: 최단경로

이걸 풀면 다익스트라 연습이 잘 된다. 행렬로 풀면 메모리초과가 뜨고, 인접리스트로만 풀면 시간초과가 뜬다. PQ만으론 안해봤는데, PQ랑 인접리스트랑 중복으로 쓰니까 해결이 되었다.

 

순서대로 체크포인트:

1. 노드를 만들고 Comparable 상속해준다. ->PQ에서 써먹어야 하니까.
   글고, 하다보니까 인접리스트에 쓸때랑, PQ에 쓸때해서 총 두번쓰이는데 생성자가 다르게 해놨음.
2. 39번라인은 전형적으로 해왔던, 인접리스트 이어줄때 하는거임. adjList[2]는 2번 정점이랑 연결된 다른 정점들을 의미하며, 그 정점이 Node(3,10,link)라면 2번에서 3번으로 가는데 10만큼의 비용이 걸린다는 것임. 2번 정점에 붙어있는(한방에 갈수있는) 정점이 여러개일 수 있으니까 걍 묶어놓은거임
3. pq는 59번라인에서 추가되는데, distance[]에서 새로 업데이트된 원소의 인덱스(=정점)와 정보를 넣어줌. 이때 생성자 인자는 두개인데, 하나는 업뎃된 정점번호이고, 또하나는 distance이다. 그니까 pq.offer(new Node(2,6))이면 distance[2]=6 이 갱신되었다는 거다. 즉 출발점(start)에서 산건너 강건너 2번에 도착하는데 6만큼 걸린다는 거다.
   암튼 pq에 넣었으니 distance[] 원소 중 새로 업데이트된 원소의 인덱스(=정점)이 weight 기준으로 정렬되어 들어가게 된다. 
   tmi로 52,53번째 줄은 없어도 잘 돌아가긴한다. 불안하면 넣으삼(백준 돌려보니까 시간도 100ms정도 차이나긴 하는데 치명적이지 않음)
4. 그럼 인접리스트는 어디서쓰이냐? 56번 라인에서처럼 쓰임. 이전에는 하면 기존(저 위에 처음쓴 코드보삼)에 V번 돌면서 일일히 current 정점에 연결된 갈 수 있는 간선이 있나없나 체크해야 했는데, 이젠 Node로 연결되어있으니까 바로 정점으로 딱딱 이동함.

public class BOJ_1753최단경로_인접리스트andPQ {
	static int V, E, start;

	static class Node implements Comparable<Node>{
		int vertex;
		int weight;
		Node link;
		
		public Node(int vertex, int weight, Node link) {
			this.vertex = vertex;
			this.weight = weight;
			this.link = link;
		}
		public Node(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		start = sc.nextInt();
		
		int[] dist = new int[V+1];
		Node[] adjList = new Node[V+1];//1~V
		boolean[] visited = new boolean[V+1];
		
		for(int i=0; i<E; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int w = sc.nextInt();
			adjList[from] = new Node(to,w,adjList[from]);
		}
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start,0));
		
		while(!pq.isEmpty()) {
			//dist에서 젤 가까운 애 찾기
			Node node = pq.poll();
			int current = node.vertex;
			if(visited[current]) continue;
			visited[current] = true;
			
			//뽑힌 점점에 연결된 간선들 업데이트
			for(Node temp = adjList[current]; temp!=null; temp = temp.link) {
				if(!visited[temp.vertex] && dist[temp.vertex] > dist[current]+temp.weight) {
					dist[temp.vertex] = dist[current]+temp.weight;
					pq.offer(new Node(temp.vertex, dist[temp.vertex]));
				}
			}
		}
		
		for(int i=1; i<dist.length; i++) {
			if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(dist[i]);
		}
		
		
	}

}

79