백준 1753 - 최단경로

Java

1753번 - 최단경로

문제

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

접근 방법

다익스트라를 통하여 시작 점에서 각 정점으로 가는 최단 거리를 구한다.
간선의 정보를 2차원 배열로 저장하면, 정점의 개수가 최대 20,000이므로, 20000 x 20000 x 4byte > 256MB가 된다.
따라서 주어진 간선의 정보만 들어가 있는 Node class와 Priority Queue를 통하여 Dijkstra를 구현하였다.

코드

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

public class Main {
	
	static class Node implements Comparable<Node> {
		int end;			// 현재 정과 연결 되어 있는 끝 정점
		int weight;			// 가중치
		
		public Node(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return Integer.compare(weight,o.weight);
		}
	}
	
	static int v, e, start;
	static int[] distance;
	static boolean[] vis;
	static List<List<Node>> graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	v = stoi(stk.nextToken());
    	e = stoi(stk.nextToken());
    	graph = new ArrayList<List<Node>>();
    	
    	distance = new int[v + 1];		// 시작점에서 각 정점으로 가는데 걸리는 최소 비용
    	vis = new boolean[v + 1];
    	for(int i = 0; i < v + 1; i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	start = stoi(br.readLine());
    	
    	for(int i = 0; i < e; i++) {
    		stk = new StringTokenizer(br.readLine());
    		int st = stoi(stk.nextToken());
    		int end = stoi(stk.nextToken());
    		int w = stoi(stk.nextToken());
    		graph.get(st).add(new Node(end, w));	// 각 정점 st에서 이어지는 정점 end와 weight
    	}
    	
    	Arrays.fill(distance, Integer.MAX_VALUE);
    	distance[start] = 0;
    	
    	PriorityQueue<Node> queue=new PriorityQueue<Node>();
		queue.offer(new Node(start,distance[start]));
    	
		while(!queue.isEmpty()){
			Node current=queue.poll();
        	
			int curN = current.end;
        	if(vis[curN])continue;
        	
        	vis[curN]=true; // 선택 정점 방문 처리
			
			//step2: current정점을 경유지로 하여 갈수 있는 다른 방문하지 않은 정점들에 대한 처리
			for(Node node : graph.get(curN)) {
				if(node.weight + distance[curN] < distance[node.end]) {
					distance[node.end] = distance[curN] + node.weight;
	                queue.add(new Node(node.end, distance[node.end]));
				}
			}
		}
    	
    	for(int i = 1; i <= v; i++) {
    		if(distance[i] != Integer.MAX_VALUE)
    			System.out.println(distance[i]);
    		else
    			System.out.println("INF");
    	}
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐⭐⭐

후기

개선할 점

없