[백준(Baekjoon)][자바(java)] 1753 : 최단 경로 / 최단 경로

 

www.acmicpc.net/problem/1753

1753번: 최단경로

 

문제 풀이

 

-  방향 그래프의 다익스트라( dijkstra ) 문제

  ☞  하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구하는 단일 시작점 최단 경로 문제. 음의 가중치를 허용하지 않음. 

-  인접 리스트로 그래프 표현 ( 데이터 접근/탐색 시 ArrayList가 LinkedList 보다 빠름 )

-  우선순위 큐( PriorityQueue ) 이용  ☞  거리가 작은 순으로 빠져나옴

-  ( 배열의 0부터 사용하기 위해 정점 번호 입력받을 때 1씩 뺌 )

 

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

public class Main {
	
	static class Path implements Comparable<Path> {
		int v, d;	// vertex num, distance from start vertex
		Path( int v, int d ) {
			this.v = v;
			this.d = d;
		}
		@Override
		public int compareTo( Path o ) {
			return d - o.d;
		}
	}
	
	static class Node {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	public static int[] dijkstra( int d[], List<List<Node>> e, int s, int n ) {
		int i, u, v, d_u, w, d_v; Path p;
		for( i = 0; i < n; i++ )
			d[i] = i == s ? 0 : Integer.MAX_VALUE; 
		PriorityQueue<Path> pq = new PriorityQueue<>();
		pq.add( new Path( s, 0 ) );
		while( !pq.isEmpty() ) {
			p = pq.remove();
			u = p.v; 
			d_u = p.d;
			for( Node nd : e.get(u) ) {
				v = nd.v;	// connected vertex num
				w = nd.w;	// connected weight
				d_v = d_u + w;
				if( d[v] > d_v ) {
					pq.add( new Path( v, d_v ) );
					d[v] = d_v;
				}
			}
		}
		return d;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
		
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int v_num = Integer.parseInt( st.nextToken() ), 
		    e_num = Integer.parseInt( st.nextToken() ), 
		    v_start = Integer.parseInt( br.readLine() ) - 1, i, j;	
		// vertex_num, edge_num, vertex_start
		int d[] = new int[v_num];			    // vertex
		List<List<Node>> e = new ArrayList<>();	// edge
		int a[] = new int[3];
		for( i = 0; i < v_num; i++ )
			e.add( new ArrayList<Node>() );
		for( i = 0; i < e_num; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ )
				a[j] = Integer.parseInt( st.nextToken() ) - 1;
			a[2]++;
			e.get( a[0] ).add( new Node( a[0], a[1], a[2] ) );
		}
		br.close();
		
		d = dijkstra( d, e, v_start, v_num );
		
		for( int n : d )
			bw.write( ( n == Integer.MAX_VALUE ? "INF" : n ) + "\n" );
		
		bw.flush();
		bw.close();
        
	}
    
}