[Java] 백준 5972번: 택배 배송

[문제 바로 가기] - 택배 배송

💡 접근 방식

다익스트라로 풀이하는 문제로 처음엔 BFS로 접근했다가 메모리 초과, 런타임 에러로 두드려 맞고 풀이를 참고했다 (^^)

연결 리스트를 선언하여 각 노드와 해당 노드와 연결된 노드, 그 가중치(소의 수)를 입력해준다. PriorityQueue를 이용하여 가중치가 작은 순서대로 정렬되도록 하며 가장 작은 값을 갱신해주고 큐에 넣는 것을 반복해주면 된다!

풀이

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

public class Main {
	public static class Node {
		int node, value;
		
		Node(int node, int value) {
			this.node = node;
			this.value = value;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		List<Node>[] list = new ArrayList[N + 1];
		
		for (int i = 0; i <= N; i++) {
			list[i] = new ArrayList<Node>(); 
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			list[num1].add(new Node(num2, value));
			list[num2].add(new Node(num1, value));
		}

		int[] dist = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		
		dist[1] = 0;		
		
		PriorityQueue<int []> queue = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
		queue.add(new int[] {1, 0});
		
		while (!queue.isEmpty()) {
			int cur[] = queue.poll();
			int value = cur[0];
			int sum = cur[1];
			
			for (int i = 0; i < list[value].size(); i++) {
				int v = list[value].get(i).node;
				int weight = list[value].get(i).value;
				
				if (dist[v] > dist[value] + weight) {
					dist[v] = dist[value] + weight;
					queue.add(new int[] {v, dist[v]});
				}
			}
		}
		
		System.out.println(dist[N]);
	}
}