백준 1916번: 최소비용 구하기

문제 설명

• https://www.acmicpc.net/problem/1916

접근법

• 다익스트라 알고리즘으로 최단거리를 구하는 문제입니다.

정답

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

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		HashMap<Integer,List<Node>> graph = new HashMap<Integer,List<Node>>();
		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int d = sc.nextInt();
			if(graph.containsKey(from)) {
				graph.get(from).add(new Node(from,to,d));
			}else {
				List<Node> temp = new ArrayList<Node>();
				temp.add(new Node(from,to,d));
				graph.put(from, temp);
			}
		}
		int start = sc.nextInt();
		int end = sc.nextInt();
		System.out.println(Dijkstra(start,end,N,graph));
	}
	
	public static int Dijkstra(int start, int end ,int N, HashMap<Integer,List<Node>> graph) {
		int[] d = new int[N+1];
		Arrays.fill(d, Integer.MAX_VALUE);
		boolean[] v = new boolean[N+1];
		d[start] = 0;
		for (int i = 0; i < N; i++) {
			int current = Integer.MAX_VALUE;
			int currentIdx = start;
			for (int j = 1; j <= N; j++) {
				if(!v[j] && current > d[j]) {
					current = d[j];
					currentIdx = j;
				}
			}
			
			v[currentIdx] = true;
			if(currentIdx == end) return d[end];
			if(!graph.containsKey(currentIdx)) continue;
			for (Node e : graph.get(currentIdx)) {
				if(!v[e.to] && d[e.to] > d[currentIdx] + e.d) {
					d[e.to] = d[currentIdx] + e.d;
				}
			}
		}
		return -1;
	}
	
	static class Node{
		int from;
		int to;
		int d;

		public Node(int from, int to, int d) {
			super();
			this.from = from;
			this.to = to;
			this.d = d;
		}
		
		@Override
		public String toString() {
			return "Node [from=" + from + ", to=" + to + ", d=" + d + "]";
		}
		
		
		
	}

}