My Dev Blog

<우선순위 큐를 활용한 풀이>

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class DijkstraByPriorityQueue {
	
	public static int n = 6; // 노드의 개수
	public static int INF = 1000000; // 무한대를 의미
	public static HashMap<Integer, ArrayList<Node>> nodeListMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드의 인덱스로부터 전체 노드까지의 인덱스와 거리를 담을 리스트
	public static HashMap<Integer, Integer> minDistanceMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드까지의 최단거리(출발 노드로부터)
	
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 생성 // 출발 노드로부터 현재 최단거리에 있는 노드부터 우선적으로 빼내어 체크하기 위함(출발 노드로부터 현재 최단거리에 있는 노드를 체크해야 다른 노드들까지의 최단거리 갱신의 가능성이 있기 때문)
		Node pqNode; // 우선순위 큐에서 빼낸 노드를 담을 변수(출발 노드로부터 현재 최단거리에 있는 노드)
		ArrayList<Node> nodeList; // 우선순위 큐에서 빼낸 (출발 노드로부터 현재 최단거리)노드를 거쳐서 체크할 타겟 노드 리스트

		// 각 노드까지의 최단거리 초기화
		for (int key : nodeListMap.keySet()){ // 0 ~ 5
			minDistanceMap.put(key, INF); // 모든 최단거리 무한대로 초기화
		}
        
		minDistanceMap.put(start, 0); //출발 노드까지의 최단거리는 0으로 SET
        
		pq.add(new Node(start, 0)); // 출발 노드를 우선순위 큐에 추가 // 최단거리가 갱신되었으므로 우선순위 큐에 추가 => 이 최단거리를 거쳐 다른 노드들까지의 최단거리도 갱신될 수 있기 때문

		while (!pq.isEmpty()) { // 더 이상 최단거리 갱신이 불가할 때까지 반복

			pqNode = pq.poll(); // 출발 노드로부터 현재 최단거리에 있는 노드

			if (pqNode.getDistance() > minDistanceMap.get(pqNode.getIndex())) { // 최단거리 갱신이 가능한지 체크
				continue;
			}
            
			nodeList = nodeListMap.get(pqNode.getIndex()); // 현재 최단거리에 있는 노드를 거쳐서 체크할 타겟 노드 리스트
            
			for (Node node : nodeList) { // 타겟 노드 0 ~ 5 모두 체크
                
				if (pqNode.getDistance() + node.getDistance() < minDistanceMap.get(node.getIndex())) { // 출발 노드로부터 현재 최단거리에 있는 노드를 거쳐서 타겟 노드로 가는 거리가 타겟 노드의 최단거리보다 작을 경우
					minDistanceMap.put(node.getIndex(), pqNode.getDistance() + node.getDistance()); // 타겟 노드의 최단거리 갱신
					pq.add(new Node(node.getIndex(), pqNode.getDistance() + node.getDistance())); // 타겟 노드 우선순위 큐에 추가
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < n; i++) { // 0 ~ 5
			nodeListMap.put(i, new ArrayList<Node>()); // key값 0 ~ 5(각 노드 인덱스)마다 Node 정보를 담을 리스트 생성
		}
		
		nodeListMap.get(0).add(new Node(0, 0)); // 0번 노드로부터 0번 노드까지의 거리 0
		nodeListMap.get(0).add(new Node(1, 2)); // 0번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(0).add(new Node(2, 5)); // 0번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(0).add(new Node(3, 1)); // 0번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(0).add(new Node(4, INF)); // 0번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(0).add(new Node(5, INF)); // 0번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(1).add(new Node(0, 2)); // 1번 노드로부터 0번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(1, 0)); // 1번 노드로부터 1번 노드까지의 거리 0
		nodeListMap.get(1).add(new Node(2, 3)); // 1번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(1).add(new Node(3, 2)); // 1번 노드로부터 3번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(4, INF)); // 1번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(1).add(new Node(5, INF)); // 1번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(2).add(new Node(0, 5)); // 2번 노드로부터 0번 노드까지의 거리 5
		nodeListMap.get(2).add(new Node(1, 3)); // 2번 노드로부터 1번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(2, 0)); // 2번 노드로부터 2번 노드까지의 거리 0
		nodeListMap.get(2).add(new Node(3, 3)); // 2번 노드로부터 3번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(4, 1)); // 2번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(2).add(new Node(5, 5)); // 2번 노드로부터 5번 노드까지의 거리 5
		
		nodeListMap.get(3).add(new Node(0, 1)); // 3번 노드로부터 0번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(1, 2)); // 3번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(3).add(new Node(2, 3)); // 3번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(3).add(new Node(3, 0)); // 3번 노드로부터 3번 노드까지의 거리 0
		nodeListMap.get(3).add(new Node(4, 1)); // 3번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(5, INF)); // 3번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(4).add(new Node(0, INF)); // 4번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(1, INF)); // 4번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(2, 1)); // 4번 노드로부터 2번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(3, 1)); // 4번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(4, 0)); // 4번 노드로부터 4번 노드까지의 거리 0
		nodeListMap.get(4).add(new Node(5, 2)); // 4번 노드로부터 5번 노드까지의 거리 2
		
		nodeListMap.get(5).add(new Node(0, INF)); // 5번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(1, INF)); // 5번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(2, 5)); // 5번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(5).add(new Node(3, INF)); // 5번 노드로부터 3번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(4, 2)); // 5번 노드로부터 4번 노드까지의 거리 2
		nodeListMap.get(5).add(new Node(5, 0)); // 5번 노드로부터 5번 노드까지의 거리 0
		
		dijkstra(0); // 출발 노드 0
		
		for (int i = 0; i < n; i++) { // 0 ~ 5
			System.out.print(minDistanceMap.get(i) + " "); // 각 노드까지의 최단거리 출력(출발 노드로부터)
		}
	}
}

public class Node implements Comparable<Node> {
	
	private int index = 0; // 노드의 번호
	private int distance = 0; // 노드의 거리
	
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
	
	public int getIndex() {
		return this.index;
	}
	
	public int getDistance() {
		return this.distance;
	}

	@Override
	public int compareTo(Node otherNode) {
		// TODO Auto-generated method stub
		return this.distance - otherNode.distance; // distance 기준 오름차순 정렬 // 1, 2, 3, ...
//		return otherNode.distance - this.distance; // distance 기준 내림차순 정렬 // ..., 3, 2, 1
	}
}

출력 결과 : 0 2 3 1 2 4

Dijkstra(다익스트라) 알고리즘 우선순위 큐 문제 풀이 Java

<선형 탐색 풀이>

public class Dijkstra {
	
	public static int n = 6;
	public static int INF = 1000000;
	public static int[][] arr = {{0, 2, 5, 1, INF, INF}, {2, 0, 3, 2, INF, INF}, {5, 3, 0, 3, 1, 5}, {1, 2, 3, 0, 1, INF}, {INF, INF, 1, 1, 0, 2}, {INF, INF, 5, INF, 2, 0}};
	public static boolean[] visited = new boolean[n];
	public static int[] minDistance = new int[n];
	
	
	// 선형 탐색 풀이
	public static int getSmallestValueIndex() { // 방문하지 않은 정점 중 최소 거리를 갖는 정점의 인덱스를 반환해주기 위한 함수
		int minValue = INF;
		int minValueIndex = 0;
		
		for (int i = 0; i < n; i++) {
			
			if (!visited[i] && minDistance[i] < minValue) { // 방문하지 않은 정점 중 최단 거리인 정점의 인덱스 찾기
				minValue = minDistance[i];
				minValueIndex = i;
			}
		}
		return minValueIndex;
	}
	
	public static void dijkstra(int startIndex) {
		
		// STEP 1. 입력받은 시작 인덱스토부터 각 정점까지의 거리를 최단 거리로 SET
		for (int i = 0; i < n; i++) {
			minDistance[i] = arr[startIndex][i]; // 시작 인덱스 0으로부터 각 정점까지의 거리를 최소값으로 세팅
		}
		// {0, 2, 5, 1, INF, INF}
		
		// STEP 2. 시작 인덱스 방문처리
		visited[startIndex] = true;
		// {true, false, false, false, false, false}
		
		// STEP 3 ~ STEP 6
		for (int i = 0; i < n - 2; i++) { // n - 2를 쓰는 것이 더 효율적인 이유 : 아래에 ★ 주석 부분 참고
			
			// STEP 3. 방문하지 않은 정점 중 최소 거리를 갖는 정점 인덱스 가져오기
			int minIndex = getSmallestValueIndex(); // 바로 위의 반복문은 getSmallestValueIndex(방문하지 않은 최소 거리를 갖는 정점의 인덱스를 가져오는 함수)를 호출해야 하는 횟수를 의미
			// minIndex : 3
			
			// STEP 4. 최소 거리를 갖는 정점 방문처리 => 현재 상테에서 최소 거리를 갖는다는 말은, 다른 정점(최소 거리보다 큰 값)을 거쳤을 경우 값이 절대 갱신될 수 없음을 의미
			visited[minIndex] = true;
			// {true, false, false, true, false, false}
			
			// STEP 5. 최소 거리를 갖는 정점으로부터 방문하지 않은 다른 정점까지의 거리 체크
			for (int j = 0; j < n; j++) {
				
				if (!visited[j]) { // 방문하지 않은 정점이라면
					
					// STEP 6. 최소 거리를 갖는 정점을 거쳐서 다른 정점을 가는 거리가 더 작을 경우 갱신
					if (minDistance[minIndex] + arr[minIndex][j] < minDistance[j]) { // 최소 거리를 갖는 정점까지의 거리 + 최소 거리 정점으로부터 방문하지 않은 다른 정점까지의 거리가 다른 정점까지의 최소 거리보다 작다면
						minDistance[j] = minDistance[minIndex] + arr[minIndex][j]; // 거쳐갔을 경우의 거리 값이 더 작으므로 최소 거리 갱신
					}
				}
			}
		} 
	}
	
	// ★ 방문하지 않은 최소 거리를 갖는 정점의 인덱스를 가져와야 하는 횟수를 의미 => 이미 방문한 startIndex가 있으므로 반복 횟수 -1,
	// ★ n - 1로 했을 경우 반복문의 흐름 상 getSmallestValueIndex에서 나오는 마지막 인덱스는 STEP 4에서 방문처리가 되고(모두 방문을 마친 상태), STEP 5 반복문이 아무 의미가 없는 상황이 된다.
	// ★ 이 문제는 minDistance를 갱신하기 위함이지, 방문에 목적이 있는 것이 아니므로 횟수를 한번 더 줄여 n - 2를 해도 같은 결과가 나온다.

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		dijkstra(0); // 시작 인덱스 0
		
		for (int i = 0; i < minDistance.length; i++) {
			System.out.print(minDistance[i] + " "); // 다익스트라 이후 갱신된 최단 거리 출력
		}
	}
}

STEP 3 ~ STEP 6 부분의 첫 번째 반복문의 횟수가 n도, n-1도 아닌 n-2인 이유는

방문하지 않은 노드 중 시작 노드로부터 최단 거리에 있는 노드의 인덱스를 가져와야 하는 횟수를 의미 =>

이미 방문한 startIndex가 있으므로 반복 횟수 -1,

n - 1로 했을 경우 반복문의 흐름 상 getSmallestValueIndex에서 나오는 마지막 인덱스는 STEP 4에서 방문처리가 되고

(모두 방문을 마친 상태), STEP 5 반복문이 아무 의미 없는 상황이 된다.

​

이 문제는 minDistance를 갱신하기 위함이지, 방문에 목적이 있는 것이 아니므로 횟수를 한번 더 줄여

n - 2를 해도 같은 결과가 나온다.

출력 결과 : 0 2 3 1 2 4

Dijkstra(다익스트라) 알고리즘 선형 탐색 문제 풀이 Java