[백준(Baekjoon)][자바(java)] 1504 : 특정한 최단 경로 / 최단 경로

 

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

문제 풀이

 

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

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

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

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

-   다익스트라 알고리즘을 총 3번 실행함

 ☞  vs ( start vertex ), ve ( end vertex ), v1 ( vertex1 ), v2 ( vertex2 ) 라고 할 때,
      way1  :  vs ~ v1 ~ v2 ~ ve
      way2  :  vs ~ v2 ~ v1 ~ ve
      중에서 거리가 더 짧은 경로가 답이 된다
      방향이 없으므로 v1 ~ v2 와 v2 ~ v1 가 같음

 ☞  1번  =>  v1(또는 v2)를 시작 정점으로 하여 v2(또는 v1)까지의 최단 거리를 구함
        2번  =>  vs를 시작 정점으로 하여 각각 v1, v2까지의 최단 거리 구함
      3번  =>  ve를 시작 정점으로 하여 각각 v1, v2까지의 최단 거리 구함

 

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 ) );
		
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int v_num = Integer.parseInt( st.nextToken() ), 
		    e_num = Integer.parseInt( st.nextToken() ), i, j;	
		    // vertex_num, edge_num
		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] ) );
			e.get( a[1] ).add( new Node( a[1], a[0], a[2] ) );
		}
		st = new StringTokenizer( br.readLine() );
		int vs = 0, ve = v_num – 1, 
  		    v1 = Integer.parseInt( st.nextToken() ) - 1, 
		    v2 = Integer.parseInt( st.nextToken() ) - 1;
		    // vertex_start, vertex_end, vertex_1, vertex_2
		br.close();
		
		int way1, way2, dist, path = 0, max = Integer.MAX_VALUE; // way, distance, path 
		d = dijkstra( d, e, v1, v_num );
		dist = d[v2]; 
		if( dist == max )
			path = -1;
		else {
			way1 = way2 = dist;
			d = dijkstra( d, e, vs, v_num );
			way1 = d[v1] == max || way1 == max ? -1 : way1 + d[v1]; 
			way2 = d[v2] == max || way2 == max ? -1 : way2 + d[v2]; 
			d = dijkstra( d, e, ve, v_num );
			way1 = d[v2] == max || way1 == max ? -1 : way1 + d[v2]; 
			way2 = d[v1] == max || way2 == max ? -1 : way2 + d[v1]; 
			path = ( way1 == -1 || way2 == -1 ) ? -1 : Math.min( way1, way2 );
		}
		System.out.println( path );
	}

}

// 방향이 없음

// way 1 : vs ~ v1 ~ v2 ~ ve
// way_2 : vs ~ v2 ~ v1 ~ ve
// dist : v1 ~ v2 ( = v2 ~ v1 )

// ( v1 -> v2 ) = ( v2 -> v1 )	// 한 개만 구함 ( v1를 시작정점으로 하여 v2까지 이르는 최단경로 or v2를 시작정점으로 하여 v1까지 이르는 최단경로 )
// ( v2 -> ve ) = ( ve -> v2 )	// ve를 시작정점으로 하여 v2, v1까지 이르는 최단경로 구하기
// ( v1 -> ve ) = ( ve -> v1 )	//