백준 1753 <최단 경로>

 

이 문제를 풀면서 두 가지 방법으로 문제를 풀어 볼 것이다. 

 

1. 우선순위 큐를 사용하지 않은 최단 경로
2. 우선순위 큐를 사용한 최단 경로

이렇게 두가지 방법으로 풀어 본 이유는 우선순위 큐를 사용하는 것이 과연 빠른가? 하는 마음에서 사용하기로 했다.

 

<우선순위 큐를 사용하지 않은 최단 경로>

차이가 있는 부분은 가장 작은 최소를 어떻게 찾을 수 있을까 부분이다.

 

 전체 정점을 돌면서 방문하지 않았고 최소 거리인 점을 찾는 부분이다.

 

<우선순위 큐를 사용한 최단 경로>

 

우선 순위 큐를 사용하게 되면 방문했던 곳이면 넘어가 주면 되고 그렇지 않은 경우에 가장 작은 경로를 반환해 주기 때문에 쉽게 구현을 할 수 있다.

 

즉 우선 순위큐를 사용하지 않으면 v^2를 요구하게 된다면  사용하게 된다면 vlogv+ elogv 시간이 걸려 시간을 단축할 수 있다.

 

 

 

이런 식으로 흐름이 진행되게 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static class po implements Comparable<po>{
		int nu;
		int dis;
		public po(int nu,int dis){
			this.nu=nu;
			this.dis=dis;
		}
		@Override
		public int compareTo(po arg0) {
			// TODO Auto-generated method stub
			if(this.dis>arg0.dis)
				return 1;
			return -1;
		}
	}
	static PriorityQueue<po> q=new PriorityQueue<po>();
	static ArrayList<po> num[];
	static int di[];
	static int v,e,k,count;
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st=new StringTokenizer(kb.readLine());
		v= Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		di=new int[v+1];
		visit=new boolean[v+1];
		num=new ArrayList[v+1];
		k=Integer.parseInt(kb.readLine());
		for(int i=1;i<=v;i++) {
			num[i]=new ArrayList<po>();
		}
		for (int i = 1; i <=e ; i++) {
			st=new StringTokenizer(kb.readLine());
			num[Integer.parseInt(st.nextToken())].add(new po(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
		count++;
		q.add(new po(k,0));
		start();
		
		for(int i=1;i<=v;i++) {
			if(i!=k&&di[i]==0)
				System.out.println("INF");
			else
				System.out.println(di[i]);
		}
		
	}
	public static void start() {
		while(!q.isEmpty()) {
			po a=q.remove();
			if(visit[a.nu])
				continue;
			visit[a.nu]=true;
			di[a.nu]=a.dis;
			for(int i=0;i<num[a.nu].size();i++) {
				po h=num[a.nu].get(i);
				if(!visit[h.nu])
					q.add(new po(h.nu,a.dis+h.dis));
			}
		}
	}
}