[BJ] 백준 1753 최단경로(JAVA)

문제

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

 

풀이 방법

이 문제는 다익스트라를 이용하는 문제였던걸로 기억한다.
시작 위치에서부터 가장 최소인 경로를 출력하면 된다.
나는 우선 정점과 가중치를 저장하기 위한 클래스를 하나 선언해줬고, 우선 순위큐를 사용했다. 
우선순위 큐에는 현재 시작점으로 부터 가장 가중치가 작은걸 우선으로 정렬하도록 선언했다. 
우선순위 큐에서 하나씩 꺼내면서 꺼낸걸 방문 체크해주고, 꺼낸걸 기준으로 꺼낸 점접의 인접 점들을 보면서 
꺼낸 것을 경유지로 간다면 더 작은 경로인 경우들만 경로를 업데이트 해주고, 우선순위 큐에다가 넣어주는 식으로 구현했다.

 

제출 코드

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

import sun.security.provider.certpath.Vertex;

public class BJ_1753_최단경로 {
	static class Node {
		int vertex, weight;
		Node link;
		public Node(int vertex, int weight, Node link) {
			this.vertex = vertex;
			this.weight = weight;
			this.link = link;
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int V = Integer.parseInt(st.nextToken());
		int E =  Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int K =   Integer.parseInt(st.nextToken()); //시작 정점

		Node[] adjList = new Node[V+1];
		boolean[]visited = new boolean[V+1];
		int[] distance =new int[V+1]; 
		
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		
		for (int i = 0; i < E; i++) { //인접 리스트
			st = new StringTokenizer(br.readLine());
			int from   = Integer.parseInt(st.nextToken());
			int to   = Integer.parseInt(st.nextToken());
			int weight   = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, weight,adjList[from] );
		}
		
		Arrays.fill(distance,Integer.MAX_VALUE);
		
		distance[K] = 0; 
		pq.add(new int[]{K,distance[K]}); //정점 번호와 거리의 최소값을 넣기
		
		while(!pq.isEmpty()) {
			//최소 비용 찾기
			int[] temp = pq.poll();
			int idx = temp[0];
			if(visited[idx]) continue;
			visited[idx] =true;
			
			//선택한 걸 경유지로 해서 최소 비용 업데이트
			for (Node j = adjList[idx] ; j != null ; j = j.link) {
				if(!visited[j.vertex]  && distance[j.vertex] > distance[idx]+ j.weight) {
					distance[j.vertex] = distance[idx]+ j.weight;
					pq.add(new int[] {j.vertex, distance[j.vertex]});
				}확인
			}
		}	
		for (int i = 1; i <= V; i++) {
			if(distance[i] != Integer.MAX_VALUE)sb.append(distance[i]+"\n");
			else sb.append("INF\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
}