백준[1753] 최단경로

박지호·2022년 7월 15일
0

백준 1753 최단경로

INPUT

정점 개수, 간선 개수가 주어지고,
그 이후로는 (시작노드, 도착노드, 가중치)가 간선의 개수만큼 주어진다.

OUTPUT

시작노드에서 자신을 포함한 모든 노드까지의 최단 경로값을 출력한다. 이때 만약 시작노드에서 갈 수 없는 노드라면 INF로 출력한다.

최단 경로 알고리즘

최단 경로 알고리즘은 크게 세 가지이다. + bfs

  1. 다익스트라 알고리즘 (Dijkstra Algorithm)
  2. 벨만 - 포드 알고리즘 (Bellman - Ford - Moore Algorithm)
  3. 플로이드 - 워셜 알고리즘 (Floyd - Warshall Algorithm)

각각 알고리즘의 상세는 다른 포스트에 정확히 정리하고자 한다.


각 알고리즘을 사용하는 상황은 다음과 같다.


1. 다익스트라 알고리즘
: 가중치가 모두 양수인 경우, 한 노드에서 다른 노드까지의 최단 경로, 최단 거리를 찾기에 용이하다.

2. 벨만-포드 알고리즘
: 가중치에 음수도 있을 경우에, 한 노드에서 다른 노드까지의 최단 경로, 최단 거리를 찾기에 용이하다. 이때 음의 사이클이 존재하는지도 파악 가능!

3. 플로이드-워셜 알고리즘
: 노드끼리의 전체 쌍에 대해 모든 최단 경로를 찾기에 용이하다.


물론 벨만-포드 알고리즘은 다익스트라 알고리즘을 대체할 수 있지만, 다익스트라의 시간복잡도가 훨씬 낮으므로 음의 가중치가 존재하지 않을 때는 다익스트라를 쓰도록 하자.

다익스트라 알고리즘

그림으로 이해해보자

주요 메커니즘은 각 정점을 한 번씩만 들어간다는 것이다.
각 정점에 다다르면 해당 정점이 출발 정점인 간선을 찾아 최단 거리를 갱신하도록 한다. 이때 최단 거리가 갱신이 된다면 도착 정점과 cost를 min heap에 넣어준다.

min heap에서 또 하나의 원소를 꺼내서 해당 정점을 돌아보고, 최단 거리를 갱신하고, 다른 원소를 추가하고...

이렇게 min heap이 빌 때까지 반복하면 된다.

CODE

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

//도착 노드와 가중치를 저장하는 class 이다.
class Data2{
	int to; long cost;
	public Data2(int to,long cost) {
		this.to = to;
		this.cost = cost;
	}
}

public class Main {
	
	public static ArrayList<ArrayList<Data2>> aL; //인접리스트 
	public static long[] result; // 결과값
	public static boolean[] visit; // 방문 여부
	
	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 str = br.readLine();
		String []sp = str.split(" ");
		
		int V = Integer.parseInt(sp[0]); //정점의 개수
		int E = Integer.parseInt(sp[1]); //간선의 개수
		
		str = br.readLine();
		int start = Integer.parseInt(str); //시작 노드
		
		//인접 리스트 초기화
		aL = new ArrayList<>();
		for(int i = 0; i<=V;i++)
			aL.add(new ArrayList<Data2>());
		
		for(int i = 0; i<E;i++) {
			str = br.readLine();
			sp = str.split(" ");
			
			// a->b (cost : c)
			int a = Integer.parseInt(sp[0]);
			int b = Integer.parseInt(sp[1]);
			int c = Integer.parseInt(sp[2]);
			
			aL.get(a).add(new Data2(b,c));
		}
		
		// 음의 가중치는 가지지 않고,
		// 한 정점에서의 각 정점까지의 최단 거리를 구하는 것이므로 
		// 다익스트라 알고리즘을 사용하면 된다.
		
		//결과 list 초기화, 방문 정보 초기화
		result = new long[V+1];
		visit = new boolean[V+1];
		
		
		for(int i = 0; i<V+1;i++) result[i] = Integer.MAX_VALUE;
		result[start] = 0;
		
		//다익스트라 실행
		Dijkstra(start);
		
		//결과 출력
		for(int i = 1; i<=V;i++) {
			if(result[i] == Integer.MAX_VALUE) {bw.write("INF"+"\n"); continue;}
			bw.write(result[i]+"\n");
		}
		
		bw.flush();
	}
	
	public static void Dijkstra(int v) {
		
		//cost 기준으로 정렬하는 우선순위 큐 (min heap) 생성
		PriorityQueue<Data2> q = new PriorityQueue<>(new Comparator<Data2>() {
			@Override
			public int compare(Data2 a,Data2 b) {
				if(a.cost > b.cost) return 1;
				else if(a.cost < b.cost) return -1;
				else return 0;
			}
		});
		
		//시작 노드와 시작노드-시작노드의 cost인 0을 넣는다.
		q.add(new Data2(v,0));

		
		while(!q.isEmpty()) {
			Data2 tmp = q.poll(); //q에서 하나를 꺼낸다.

			//꺼낸 data 확인
			int to = tmp.to;
			
			if(visit[to]) continue; //이미 방문했다면 pass
			visit[to] = true; //정점을 방문했음을 표시
			
			//꺼낸 node와 연결되어있는 간선을 체크한다.
			for(int i = 0; i<aL.get(to).size();i++) {
				Data2 next = aL.get(to).get(i);
				
				//이 방향으로 오는게 원래 저장되어있던 최소 cost값보다 작다면
				//이 경로로 오는 것이 더 최단 거리이다. --> 갱신
				if(result[next.to] > result[to]+next.cost) {
					result[next.to] = result[to]+next.cost;
					q.add(new Data2(next.to,result[next.to])); //힙에 추가
				}
			}
		}
	}

}

check

  • 다익스트라 알고리즘은 정말 정말 많이 쓰이는 최단 거리 알고리즘 이다.

  • 최단 거리 알고리즘은 크게 3가지로 나뉘며, 각 알고리즘의 쓰임을 잘 알고 쓰자.

  • 다익스트라 알고리즘이 기억이 안나면 ?
    다익스트라 ==> min heap을 쓰는 bfs 정도로만 기억하자!

0개의 댓글