[JAVA] 백준 1753 최단 경로

1753번: 최단경로 (acmicpc.net)

1753번: 최단경로

 

- 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오, 

- 단, 모든 간선의 가중치는 10 이하의 자연수이다. 

 

입력

- 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. 

- 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K가 주어진다. 

- 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수(u,v,w)가 순서대로 주어진다. 

- 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 

- 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 

 

출력

- 첫 째줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 

- 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다. 

 

 

문제 풀이 

 

다익스트라 알고리즘 

[Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

[Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로)

 

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘 (velog.io)

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘

 

- 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작 노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용할 수 있다. 

 

- 하나의 정점에서 출발하는 최단 거리를 구함

 

<진행 과정>

 

1) 거쳐 갈 혹은 시작할 노드를 방문 후 방문 처리 한다. 

2) 방문한 노드에서 이동할 수 있는 노드들을 탐색한다. 

3) 탐색된 노드들의 계산된 거리 비용이 현재까지 저장된 최단 거리보다 적을 경우 최단 거리를 갱신한다. 

4) 최단 거리가 갱신된 노드들 중에서 가장 작은 거리를 가지는 노드로 이동 후 방문 처리 한다. 

5) 1~4)번을 계속 반복 후 더 이상 방문할 노드가 없을 때 종료된다. 

 

출처 :  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

 

 

 

- 출발 노드는 1번이고, 1번 노드에서 다른 노드들까지 이동할 떄의 최단 거리를 구한다고 가정하고 다익스트라 알고리즘을 진행 

 

- 1번 노드를 방문 처리한 후 다른 노드들까지의 거리를 계산하기 위한 최단 거리 테이블을 만들어 준다. 

출처 :  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

 

- 최초에 최단거리 테이블을 작성할 때 시작 노드를 제외한 모든 노드들의 최단거리 값은 INF이고 시작 노드의 값은 0으로 초기화 된다. 

- 2번과 3번 노드는 그래프에서 보는 것 처럼 각 간선의 거리 값으로 최단 거리 테이블을 갱신해준다. 

- 4번과 5번 노드는 현재 1번 노드에서 방문할 수 없으므로 INF값으로 불가능을 나타내준다. 

- 갱신 여부는 false, true로 표시해준다. 

 

- 이제 최단 거리가 갱신된 노드들 중에서 가장 작은 최단거리를 가지는 노드로 이동한다. 

- 위의 예시에서는 2번 노드가 3번 노드보다 값이 더 적으므로 2번 노드로 이동후 방문 처리한다. 

 

출처 :  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

 

- 2번 노드를 방문한 후에는 이동 가능한 노드들을 탐색 후 최단거리 테이블을 갱신해줘야 한다. 

- 현재 2번 노드에서 방문 가능한 노드는 3번과 4번 노드가 있다. 

- 그러나 3번 노드는 1번 -> 3번으로 갈 때의 거리 비용이 1번 -> 2번 -> 3번으로 이동할 때의 거리 비용 값보다 적으므로 갱신되지 않는다. 

 

최단거리 테이블 3번 노드 값 < 최단거리 테이블 2번 노드 값 + 2번 노드에서 3번 노드로 이동할 때의 간선의 거리 

 

- 좌측의 값이 우측보다 클 때만 최단거리가 갱신됨

 

- 4번 노드는 1번 노드에서 이동이 불가능했지만 2번 노드를 거쳐갈 때는 이동이 가능하므로 1번 -> 2번 -> 4번 노드로 연결되는 간선의 거리 비용 값을 모두 더한 값으로 갱신해준다. 

 

최단 거리 테이블 4번 노드 값 > 최단 거리 테이블 2번 노드 값 + 2번 노드에서 4번 노드로 이동할 때의 간선의 거리 

 

 

- 이제 최단거리가 갱신된 노드 중 가장 적은 거리를 가지는 노드로 이동을 한다. 

- 위의 그림에서는 1번 노드를 방문했을 때 갱신되었던 3번 노드가 4번 노드보다 거리 값이 적으므로 3번 노드로 이동한다. 

 

출처 :  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

 

- 3번 노드를 방문 처리 후에 이동 가능한 노드를 탐색하면 현재 4번 노드로만 이동이 가능하다. 

 

최단 거리 테이블 4번 노드 값 < 최단 거리 테이블 3번 노드 값 + 3번에서 4번 노드로 이동할 때의 거리 

 

- 좌측의 값보다 우측의 값이 크기 때문에 4번 노드의 최단 거리는 갱신되지 않는다. 

 

- 이제 현재까지 최단거리가 갱신된 노드 중에서 거리가 가장 작은 노드로 이동을 진행한다. 

- 현재 갱신된 노드 목록에서 남아있는 노드는 4번 노드 1개뿐이므로 4번으로 이동한다. 

 

출처 :  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) (tistory.com)

 

- 4번 노드를 방문 처리한 후에 이동 가능한 노드를 탐색한다. 

- 현재 4번 노드에서 다른 노드들로 이동 가능한 간선이 존재하지 않기 때문에 최단 거리 테이블을 갱신하는 작업은 진행되지 않는다. 

- 다음으로 현재까지 갱신된 노드들 중에서 가장 작은 거리 값을 가지는 노드를 찾는다, 

- 그러나 갱신된 노드 목록이 비어있으므로 더 이상 방문할 노드가 존재하지 않다는 것을 알 수 있다. 

- 방문할 노드가 존재하지 않으면 알고리즘을 종료한다. 

 

- 개선된 다익스트라 알고리즘 구현을 위해 리스트 그래프 + 우선순위 큐를 사용 

- 우선순위 큐 => 가장 높은 데이터를 가장 먼저 삭제 

 

 

정답 

 

import java.util.*;
import java.io.*;

public class Main {
	//INF 값 초기화 
	static final int INF = 9999999;
	//그래프를 표현 할 2차원 List
	static List<List<Node>> graph = new ArrayList<>();
	//최단거리 테이블 
	static int result[];
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input[] = br.readLine().split(" ");
		int start = Integer.parseInt(br.readLine());
		
		//그래프 생성
		for(int i=0; i<Integer.parseInt(input[0])+1; i++) {
			graph.add(new ArrayList<>());
		}
		
		//최단 거리 테이블 생성
		result = new int[Integer.parseInt(input[0])+1];
		
		//최단거리테이블 INF로 초기화 
		Arrays.fill(result,INF);
		
		//문제에서 주어진 입력 값에 따라 그래프 초기화 
		for(int i=0; i<Integer.parseInt(input[1]); i++) {
			String temp[] = br.readLine().split(" ");
			graph.get(Integer.parseInt(temp[0])).add(new Node(Integer.parseInt(temp[1]), Integer.parseInt(temp[2])));
		}
		
		dijkstra(start);
		
		for(int i=1; i<result.length; i++) {
			if(result[i] == INF) {
				bw.write("INF");
				bw.newLine();
			}else {
				bw.write(String.valueOf(result[i]));
				bw.newLine();
			}
		}
		
		bw.flush();
		
	}
	
	//다익스트라 
	static void dijkstra(int index) {
		//최단 거리가 갱신 된 노드들을 당믈 우선순위 큐 생성
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		//최단거리테이블의 시작지점노드 값 0으로 갱신
		result[index] = 0;
		
		//우선순위 큐에 시작 노드 삽입
		pq.offer(new Node(index, 0));
		
		//우선순위 큐에 노드가 존재하면 계속 반복
		while(!pq.isEmpty()) {
			//큐에서 노드 꺼내기 
			Node node = pq.poll();
			
			//꺼낸 노드의 인덱스 및 최단거리 비용 확인
			int nodeIndex = node.index;
			int distance = node.distance;
			
			//큐에서 꺼낸 거리와 최단거리테이블의 값을 비교하여 방문처리
			//만약 현재 꺼낸 노드의 거리가 최단거리테이블의 값보다 크다면 해당 노드는 이전에 방문된 노드이다. 
			//그러므로 해당 노드와 연결된 노드를 탐색하지 않고 큐에서 다음 노드를 꺼낸다. 
			if(distance > result[nodeIndex]) {
				continue;
			}
			
			//큐에서 꺼낸 노드에서 이동 가능 한 노드들을 탐색한다. 
			for(Node linkedNode : graph.get(nodeIndex)) {
				//해당 노드를 거쳐서 다음 노드로 이동할 때의 값이 다음 이동노드의 최단거리테이블 값보다 작을 때
				if(distance + linkedNode.distance < result[linkedNode.index]) {
					//최단거리테이블의 값 갱신
					result[linkedNode.index] = distance + linkedNode.distance;
					//갱신 된 노드를 우선순위 큐에 넣어줌
					pq.offer(new Node(linkedNode.index, result[linkedNode.index]));
				}
			}
		}
	}
	
	//우선순위 큐에서 정렬기준을 잡기 위해 Comparable를 구현
	static class Node implements Comparable<Node> {
		int index;
		int distance;
		
		Node(int index, int distance) {
			this.index = index;
			this.distance = distance;
		}
		
		//최단 거리를 기준으로 오름차순 정렬
		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.distance, o.distance);
		}
	}
}