BOJ - 1753 ) 최단경로

---

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

1753번: 최단경로

---

한 노드에서 모든 노드까지의 최단거리를 구할때 벨만포드 알고리즘O(간선개수 * 노드개수 ) 이나 간선이

모두 양수인경우 다익스트라O((간선개수+노드개수)log(노드개수))의 알고리즘을 사용한다.

 

다익스트라는 PriorityQueue를 이용하면 쉽게 구현할 수있는데, 현재 발견한경로중

최소의 간선으로 거리를 갱신한다면, 이후에 업데이트 횟수가 최소가 될것이 확실하기 때문이다.

 

다만, 실수할만한 부분이 많아서.. 꼼꼼하게 체크해주어야한다.

dijkstra algorithm에 관한 설명은 아래의 gif 를 멍때리고 보면된다.

 

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#/media/%ED%8C%8C%EC%9D%BC:Dijkstra_Animation.gif

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 최단경로 {
	
	public static int shortest[];
	public static int max = 2147000000;
	public static int n,m,start;
	public static ArrayList<int []> map[];
	
	static class node{
		int s,c;
		public node(int s, int c) {
			this.s = s;
			this.c = c;
		}
	}
	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();
		input();
		dijkstra();
		for(int i = 1; i <=n; i++) {
			if(shortest[i]==max) sb.append("INF\n");
			else sb.append(shortest[i]+"\n");
		}
		System.out.print(sb);
	}
	public static void dijkstra() {
		
		PriorityQueue<node> pq = new PriorityQueue<node>(new Comparator<node>() {

			@Override
			public int compare(node o1, node o2) {
				return o1.c-o2.c;
			}
		});
		shortest[start] = 0;
		pq.add(new node(start , 0)); 
		while(!pq.isEmpty()) {
			node now = pq.poll();
			int nowpos = now.s;
			int cost = now.c;
			if(shortest[nowpos] < cost) continue;
			int size = map[nowpos].size();
			for(int i = 0 ; i < size ; i++) {
				// i 부터 갈수있는 모든 경로를 비교해보자.
				int nextpos = map[nowpos].get(i)[0];
				int nextcost = map[nowpos].get(i)[1];
				if(shortest[nextpos] > shortest[nowpos] +nextcost) {
					shortest[nextpos] = shortest[nowpos] +nextcost;
					pq.add(new node(nextpos , shortest[nowpos] +nextcost));
				}
			}
		}
	}
	public static void input() throws Exception{
		
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		shortest = new int[n+1];
		map = new ArrayList[n+1]; for(int i = 1 ; i <= n; i++) {shortest[i] = max; map[i] = new ArrayList<int []>();}
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[s].add(new int[]{e,c});
		}
	}
}

---

꼼꼼하지 못한결과...

 

문제에서 최대 노드개수가 20000개 이므로 인접행렬로 접근했다가는

4*20000^2 대략 맵만 1.5GB를 먹는신기한 현상을 볼것이다..

무조건 인접리스트로풀어야한다.