[백준 알고리즘]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를 출력하면 된다.

 

[예제]

 

---

>문제 풀이

 

말로만 듣던 다익스트라 알고리즘을 이용하여 풀어보았습니다.

 

*다익스트라 알고리즘을 풀기 위해서는 우선순위 큐에 대해서도 알아야하는데, 오래전에(?) 몇문제 안풀었더니 개념이 잘 기억이 안나더라고요... 그래서 힙 자료구조, 우선순위 큐 부터 공부하고 다익스트라 알고리즘을 이해하느라 좀 오래걸렸습니다.

**공부하기 위해 참고한 링크는(힙, 우선순위 큐, 다익스트라 알고리즘) 글 가장 아래에 달아놓겠습니다.

 

다익스트라 알고리즘은 음의 간선을 포함하지 않을 때 사용할 수 있는데, 이 글에서 가중치 w의 범위가 10 이하의 자연수라고 했으므로 사용 가능합니다.

 

 

main

* 초반에 가중치 값의 배열인 distance[]의 모든 값을 -1로 초기화 해줍니다.

* dijkstra 를 돌리고 나서도 distance[]값이 -1인 정점은 "INF"를 출력해줍니다.

 

dijkstra

우선순위에 시작지점을 offer

시작지점의 가중치 값= 0

 

**우선순위 큐가 빌 때까지 반복

1. 출발 정점에 연결되어 있는 정점들의 가중치 값을 넣어줍니다.

2. 방문한적이 없으면:

1. 방문처리를 해주고
2. 현재 정점을 기준으로 연결된 정점들 중에 가중치가 작은 포인트 부터 가중치 값들을 업데이트 해줍니다.
   연결된 정점 i의 가중치 값= min( 정점 i의 가중치 값, 현재 정점의 가중치 값+ 연결된 간선의 가중치 값);
3. 업데이트 후 정점 i를 우선순위 큐에 넣어줍니다.

 

 

문제를 풀기위해 참고한 글: https://jellyinghead.tistory.com/78

 

 

>전체 코드

 

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

public class Main {
	static int distance[];
	static LinkedList<Point> list[];
	static boolean visited[];
	
	public static void main(String [] args) throws IOException {
		int V, E, K, u, v, w;
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		V= Integer.parseInt(st.nextToken());
		E= Integer.parseInt(st.nextToken());
		K= Integer.parseInt(br.readLine());
		
		distance= new int[V+1];
		list= new LinkedList[V+1];
		visited= new boolean[V+1];
		
		Arrays.fill(distance, -1);
		for(int i=1; i<=V; i++) {
			list[i]= new LinkedList<>();
		}
		
		//입력
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            list[u].add(new Point(v, w));
		}
		
		dijkstra(K);
		
		//출력
		StringBuilder sb= new StringBuilder();
		
		for(int i=1; i<=V; i++) {
			if(distance[i]==-1) sb.append("INF\n");
			else sb.append(distance[i]+"\n");
		}
		System.out.print(sb.toString());
		br.close();
		
    }//main
	
	public static void dijkstra(int start) {
		PriorityQueue<Point> pq= new PriorityQueue<>();
		Point now;
		
		pq.offer(new Point(start, 0));
		distance[start]=0;
		
		while(!pq.isEmpty()) {
			now= pq.poll();
			
			if(visited[now.end]) continue;
			visited[now.end]= true;
			for(Point next: list[now.end]) {
				if(distance[next.end]==-1||distance[next.end]>distance[now.end] + next.weight) {
					distance[next.end]= distance[now.end] + next.weight;
					pq.offer(new Point(next.end, distance[next.end]));
				}
			}
		}
	}
	
	//정점 클래스
	static	class Point implements Comparable<Point>{
		int end, weight;
			
		public Point(int end, int weight) {
			this.end= end;
			this.weight= weight;
		}
		public int compareTo(Point p) {
			return weight - p.weight;
		}
	}
}

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

1753번: 최단경로

 

 

---

**참고한 링크)

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

[Java] Priority Queue(우선 순위 큐)

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘