[Baekjoon] 11779_최소비용 구하기 2

Gold III

문제(출처: https://www.acmicpc.net/problem/11779)

---

< 최소비용 구하기 2 >

 

문제 풀이 

 

데이크스트라 알고리즘을 사용해서 최소 비용을 구한다.

 

 my solution (Java)

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

public class _11779_ { // 최소비용 구하기 2
	static class Node implements Comparable<Node> {
		private int node;
		private int d;
		private ArrayList<Integer> list;

		public Node(int node, int d, ArrayList<Integer> list) {
			this.node = node;
			this.d = d;
			this.list = list;
		}

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

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		Node result[] = new Node[n + 1];
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
			result[i] = new Node(i, Integer.MAX_VALUE, new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			list.get(start).add(new int[] { end, cost });
		}

		st = new StringTokenizer(bf.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());

		PriorityQueue<Node> queue = new PriorityQueue<>();
		ArrayList<Integer> temp = new ArrayList<>();
		temp.add(start);
		queue.add(new Node(start, 0, temp));

		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if(node.d > result[node.node].d) {
				continue;
			}
			for (int i = 0; i < list.get(node.node).size(); i++) {
				int info[] = list.get(node.node).get(i);
				if (node.d + info[1] < result[info[0]].d) {
					ArrayList<Integer> route = new ArrayList<>();
					result[info[0]].d = node.d + info[1];
					result[info[0]].list.clear();
					for (int j = 0; j < node.list.size(); j++) {
						route.add(node.list.get(j));
						result[info[0]].list.add(node.list.get(j));
					}
					result[info[0]].list.add(info[0]);
					route.add(info[0]);

					queue.add(new Node(info[0], node.d + info[1], route));
				}
			}
		}

		bw.write(result[end].d + "\n");
		bw.write(result[end].list.size() + "\n");
		for (int i = 0; i < result[end].list.size(); i++) {
			bw.write(result[end].list.get(i) + " ");
		}
		bw.flush();
	}
}

변수)
Node : 도시 번호, 비용, 경로
n, m : 도시의 개수, 버스의 개수
list : 버스의 정보
result : 출발 도시에서 각 도시로 가는 최소 비용
start, end cost : 출발 도시 번호, 도착지의 도시 번호, 버스 비용
start, end : 출발점의 도시 번호, 도착점의 도시 번호
queue : 우선순위 큐 
temp : 출발점부터 경로 저장하는 ArrayList

 

Node

도시 번호, 버스 비용, 경로를 변수로 가진다. 우선순위는 비용이 작은 것을 우선으로 한다.

 

Main

도시의 개수와 버스의 개수를 입력받는다. 버스의 정보를 입력받아 ArrayList에 저장한다. 

출발 도시를 비용 0, 경로를 자기 자신으로 가진 Node로 만들어 우선순위 큐에 저장한 후 우선순위 큐가 빌 때까지 반복문을 실행한다. 우선순위큐에서 꺼낸 값이 현재까지의 최소 비용보다 값이 크다면 다시 돌아간다. 크지 않다면 도시와 연결된 버스를 탐색하고 최소 비용으로 업데이트 가능한 경우에 값들을 업데이트 후 우선순위 큐에 넣어준다.

 

최종 출발 도시에서 도착 도시까지 가는데 드는 최소 비용과 경로에 포함되어 있는 도시의 개수, 방문하는 도시를 순서대로 출력한다.

---

---