[백준_1753번] 최단경로

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

1753번: 최단경로

[문제]

 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

[입력 조건]

 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

[코드]

import java.util.*;

class Node implements Comparable<Node>{
	int node, cost;
	
	public Node(int node, int cost) {
		this.node=node;
		this.cost=cost;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return this.cost-o.cost;
	}
}

public class Main {
	static int v,e,k;
	static ArrayList<ArrayList<Node>> graph=new ArrayList<>();
	static int[] distance;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		v=sc.nextInt();
		e=sc.nextInt();
		k=sc.nextInt();
		
		for(int i=0;i<=v;i++)
			graph.add(new ArrayList<>());
		
		// 최단거리 저장 배열은 최댓값으로 초기화
		distance=new int[v+1];
		Arrays.fill(distance,Integer.MAX_VALUE);
		
		while(e-->0) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			
			graph.get(a).add(new Node(b,c));
		}
		
		dijkstra(k);
		
		for(int i=1;i<=v;i++) {
			if(distance[i]==Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(distance[i]);
		}
	}
	
	// 다익스트라
	static void dijkstra(int start) {
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(start,0));
		distance[start]=0;
		
		while(!pq.isEmpty()) {
			Node now=pq.poll();
			
			// 기존의 최단거리를 저장한 배열과 now 노드를 거쳐서 가는 방법 중 최단거리인 것으로 갱신 
			for(Node next:graph.get(now.node)) {
				if(distance[next.node]>distance[now.node]+next.cost) {
					distance[next.node]=distance[now.node]+next.cost;
					pq.add(new Node(next.node,distance[now.node]+next.cost));
				}
			}
		}
	}
}

 

[고찰]

 이번 문제는 다익스트라 기본 문제이다. 이전에 포스팅 했던 문제이지만 최근 다익스트라 문제들을 여러개 풀어보면서 기본 코드를 복습하는 기분으로 다시 풀어봤다. 이전 코드에서 필요없는 줄은 빼고 최대한 간결하게 다시 짜보면서 공부하는 시간을 가졌다.