[Java]백준 BaekJoon.AC 1916 : 최소비용 구하기(1753 최단경로+, 다익스트라 사용)

 

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

1916번: 최소비용 구하기

 

 

직전에 해결했던 1753번 문제의 알파 문제다.

이 문제에서 조금만 수정해도 충분히 통과할 수 있다.

https://stepping-coding.tistory.com/5

[Java]BaekJoon.AC 1753 : 최단경로 (다익스트라, 인접리스트 사용)

 

 

(짚을 부분은 INF가 없어도 된다는 점 정도.

구해야 하는 값이 정해져있기 때문에 그 값만 필요하니 굳이 INF를 설정할 필요가 없었다. 굿--!)

 

 

하지만 해결이 아닌 실력 향상이 목적이기에 복습겸 다시 작성해봤다.

 

직전에 통과한 문제라 이 문제는 술술 풀렸다,,

그래도 못다 이해한 부분을 다시 이해하기 너무 좋았다.

다른 사람의 코드를 참고했던 부분도 내 도출로 이끌어냈고 문법들(Node 리스트 생성과 오버라이딩 부분)도 다시 학습했다.

 

보다 깔끔해진 코드가 마음에 든다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static ArrayList<Node>[] list;
	static int answer[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	N = Integer.parseInt(br.readLine());
    	int M = Integer.parseInt(br.readLine());
    	
    	list = new ArrayList[N+1];
    	answer = new int[N+1];
    	
    	for(int i=0; i<N+1; i++) {
    		list[i] = new ArrayList<Node>();
    	}
    	
    	Arrays.fill(answer, Integer.MAX_VALUE);
    	
    	for(int i=0; i<M; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int go = Integer.parseInt(st.nextToken());
    		int stop = Integer.parseInt(st.nextToken());
    		int money = Integer.parseInt(st.nextToken());
    		
    		list[go].add(new Node(stop, money));
    	}
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int start = Integer.parseInt(st.nextToken());
    	int end = Integer.parseInt(st.nextToken());
    	
    	boongboong(start);
    	
    	System.out.print(answer[end]);
    	
    	
	}
	
	public static void boongboong(int start) {
		PriorityQueue<Node> queue = new PriorityQueue<>();
		boolean[] check = new boolean[N+1];
		answer[start] = 0;
		
		queue.add(new Node(start, 0));
		
		while(!queue.isEmpty()) {
			Node nod = queue.poll();
			
			if(!check[nod.arrive]) {
				for(Node temp : list[nod.arrive]) {
					if(temp.pay + answer[nod.arrive] < answer[temp.arrive]) {
						answer[temp.arrive] = temp.pay + answer[nod.arrive];
						queue.add(new Node((temp.arrive), answer[temp.arrive]));
					}
				}
				check[nod.arrive] = true;
			}
			
		}
		
	}
		

}

class Node implements Comparable<Node>{
	int arrive;
	int pay;
	
	Node(int arrive, int pay){
		this.arrive = arrive;
		this.pay = pay;
	}

	@Override
	public int compareTo(Node o) {
		return this.pay-o.pay;
	}
	
}