[백준 1753] 최단경로 in JAVA

www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

※ 풀이 방법

다익스트라 알고리즘의 기본적인 형태를 사용하는 문제였다. 

 

※ 문제 풀이 코드

//다익스트라 알고리즘

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

public class BOJ_1753 {
	static PriorityQueue<int []> pq;
	static ArrayList<int []> [] graph;
	static int [] answer;
	static boolean [] visited;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		String s=br.readLine();
		st=new StringTokenizer(s);
		
		int V=Integer.parseInt(st.nextToken());
		int E=Integer.parseInt(st.nextToken());
		
		s=br.readLine();
		int X=Integer.parseInt(s);
		
		graph=new ArrayList[V+1];
		answer=new int[V+1];
		visited=new boolean[V+1];
		pq=new PriorityQueue<int []>(new Comparator<int []>() {//우선순위 큐 우선순위 설정하는 방법
			public int compare(int [] o1, int [] o2) {
				return o1[1]-o2[1];
			}
		});
		
		for(int i=1;i<=V;i++) {//배열 및 그래프 초기화
			graph[i]=new ArrayList<int []>();
			answer[i]=987654321;
		}
		
		int a;
		int [] temp;
		int [] temp1;
		
		for(int i=0;i<E;i++) {
			s=br.readLine();
			st=new StringTokenizer(s);
			a=Integer.parseInt(st.nextToken());
			temp=new int[2];
			temp[0]=Integer.parseInt(st.nextToken());	
			temp[1]=Integer.parseInt(st.nextToken());
			
			graph[a].add(temp);
		}
		
		temp=new int[2];
		temp[0]=X;
		temp[1]=0;
		answer[X]=0;
		pq.add(temp);//시작 노드 우선순위 큐에 삽입
		
		while(!pq.isEmpty()) {
			temp=pq.remove();
			if(visited[temp[0]]) continue; //방문한 적 있는 노드인지 체크
			visited[temp[0]]=true;
			for(int [] b:graph[temp[0]]) {
				if(visited[b[0]]) continue;
				if(answer[b[0]]>temp[1]+b[1]) answer[b[0]]=temp[1]+b[1];//새로 계산한 값이 더 작을 경우 갱신
				temp1=new int[2];
				temp1[0]=b[0];
				temp1[1]=answer[b[0]];
				pq.add(temp1);
			}
		}
		
		for(int i=1;i<=V;i++) {
			if(answer[i]==987654321) bw.write("INF\n");//도달할 수 없는 경우 INF 출력
			else bw.write(answer[i]+"\n");
		}
		
		bw.flush();
		bw.close();
	}

}