관리 메뉴

공부공간

BOJ - 1753 ) 최단경로 본문

그래프 알고리즘/Dijkstra

BOJ - 1753 ) 최단경로

SangwonSeo 개발자가될수있을까? 2020. 4. 7. 23:36
728x90


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

 

1753번: 최단경로

첫째 줄에 정점의 개수 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 이하의 자연수이다. 서로 다른 두

www.acmicpc.net


한 노드에서 모든 노드까지의 최단거리를 구할때 벨만포드 알고리즘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

 

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

위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.[1][2][3] 이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의

ko.wikipedia.org

 


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를 먹는신기한 현상을 볼것이다..

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

728x90

'그래프 알고리즘 > Dijkstra' 카테고리의 다른 글

BOJ - 10282 ) 해킹  (0) 2020.10.30
BOJ - 1167 ) 트리의 지름  (0) 2020.10.25
BOJ - 1504 ) 특정한 최단 경로  (0) 2020.08.24
BOJ - 1261 ) 알고스팟  (0) 2020.04.16
BOJ - 1916 ) 최소비용 구하기  (0) 2020.04.16
BOJ - 1753 ) 최단경로  (0) 2020.04.07
0 Comments
댓글쓰기 폼