[백준 5972] 택배 배송 (자바)

백준 5972번 택배 배송 (자바)

 

 

 

출처

www.acmicpc.net/problem/5972

5972번: 택배 배송

 

 

 

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

 

 

 

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

 

 

 

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

 

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

 

 

 

접근 방법

다익스트라의 기본 알고리즘을 활용하면 풀 수 있는 문제다.

 

다익스트라 기본 시리즈..

 

기존 문제와 다른점은 문제에서 양방향이라는 조건을 제시했기 때문에 기존 리스트를 만들 때 양방향으로 만들어줘야 한다.

 

 

 

내 코드

	package dijkstra;
	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 ParcelDelivery {
	/**
	* 백준 5972 택배 배송 (https://www.acmicpc.net/problem/5972)
	*/
	private static int n,m;
	private final static int INF = (int) 1e9;
	private static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	private static int start = 1;
	private static int[] d = new int[50001];
	public static void main(String[] args) throws IOException {
	//현서 -> 찬홍
	//중간에 소들에게 여물을 줘야한다.
	//최소한의 소만 만나고 싶다.
	//N(헛간, 정점)
	//M(길, 간선)
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(reader.readLine());
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	for (int i=0; i<=n; i++) {
	graph.add(new ArrayList<>());
	}
	for (int i=0; i<m; i++) {
	st = new StringTokenizer(reader.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	int c = Integer.parseInt(st.nextToken());
	graph.get(a).add(new Node(b,c));
	graph.get(b).add(new Node(a,c));
	}
	Arrays.fill(d, INF);
	dijkstra();
	System.out.println(d[n]);
	}
	private static void dijkstra() {
	PriorityQueue<Node> pq = new PriorityQueue<>();
	pq.add(new Node(start,0));
	d[start] = 0;
	while (!pq.isEmpty()) {
	Node node = pq.poll();
	int dist = node.distance;
	int now = node.index;
	if (d[now] < dist) {
	continue;
	}
	for (int i=0; i<graph.get(now).size(); i++) {
	int cost = d[now] + graph.get(now).get(i).getDistance();
	if (cost < d[graph.get(now).get(i).getIndex()]) {
	d[graph.get(now).get(i).getIndex()] = cost;
	pq.add(new Node(graph.get(now).get(i).getIndex(), cost));
	}
	}
	}
	}//dijkstra
	static class Node implements Comparable<Node> {
	int index, distance;
	Node (int index, int distance) {
	this.index = index;
	this.distance = distance;
	}
	private int getIndex() {
	return this.index;
	}
	private int getDistance() {
	return this.distance;
	}
	@Override
	public int compareTo(Node o) {
	if (this.distance < o.distance) {
	return -1;
	}
	return 1;
	}
	}//Node
	}

view raw ParcelDelivery.java hosted with ❤ by GitHub

 

 

 

고려할 점

1. 다익스트라 알고리즘 사용할 것

2. 양방향