[Dijkstra] 1916번 - 최소비용구하기

[백준] 1916번 - 최소비용구하기

📝 나의 풀이

처음 코드를 제출하니 틀렸다고 떴다..
최단 거리가 짧은 노드를 구할 때 이렇게 단순 반복문으로 구현했는데
이 부분때문에 틀렸다고 하는건가? 하는 생각이 들었다.

public static int getSmallestNode() {
		int minDistance = INF;
		int index = 0;
		for(int i = 1; i <= city; i++) {
			if(!visited[i] && d[i] < minDistance) {
				minDistance = d[i];
				index = i;
			}
		}
		
		return index;
	}

문제를 다시 읽어보면
도시의 개수 N(1 ≤ N ≤ 1,000), 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어졌기에

최단 거리가 가장 짧은 노드를 탐색할 때
우선순위 큐를 활용하는 다익스트라 알고리즘으로 풀어야 겠다는 판단을 했다.

👩🏻‍💻 최종 코드

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;


class City implements Comparable<City>{
	int index;
	int cost;
	
	City(int index, int cost){
		this.index = index;
		this.cost = cost;
	}
	
	public int getIndex() {
		return this.index;
	}
	
	public int getCost() {
		return this.cost;
	}
	
	@Override
	public int compareTo(City c) {
		return this.cost - c.cost;
	}
}


public class Main {
	
	public static final int INF = (int) 1e9;
	static ArrayList<ArrayList<City>> graph = new ArrayList<>();
	static int d[];
	static int city;
	
	
	
	public static void dijkstra(int start) {
		PriorityQueue<City> pq = new PriorityQueue<>();
		pq.offer(new City(start, 0));
		d[start] = 0;
		
		while(!pq.isEmpty()) {
			City city = pq.poll();
			int dist = city.getCost();
			int now = city.getIndex();
			
			if(d[now] < dist) continue;
			
			for(int i = 0; i < graph.get(now).size(); i++) {
				int cost = d[now] + graph.get(now).get(i).getCost();
				
				if(cost < d[graph.get(now).get(i).getIndex()]) {
					d[graph.get(now).get(i).getIndex()] = cost;
					pq.offer(new City(graph.get(now).get(i).getIndex(), cost));
				}
			}
		}
		
	}
	

	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		city = Integer.parseInt(br.readLine());
		int bus = Integer.parseInt(br.readLine());
		
		for(int i = 0; i <= city; i++) {
			graph.add(new ArrayList<City>());
		}
		
        StringTokenizer st;
        for(int i = 0; i < bus; i++) {
        	st = new StringTokenizer(br.readLine());
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	int cost = Integer.parseInt(st.nextToken());
        	graph.get(start).add(new City(end, cost));
        }
        
        st = new StringTokenizer(br.readLine());
        int startCity = Integer.parseInt(st.nextToken());
        int endCity = Integer.parseInt(st.nextToken());
        
		d = new int[city + 1];
		Arrays.fill(d, INF);
		
		dijkstra(startCity);
		
		System.out.println(d[endCity]);
	}

}