[Baekjoon] 1916_최소비용 구하기

Gold V

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

---

< 최소비용 구하기 >

 

문제 풀이 

 

우선순위 큐를 사용해서 최소 비용을 찾는다.

 

 

 my solution (Java)

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

public class _1916_ { // 최소비용 구하기
	static ArrayList<ArrayList<City>> list;
	static boolean visited[];
	static int result[];

	static class City {
		private int num;
		private int money;

		public City(int num, int money) {
			this.num = num;
			this.money = money;
		}
	}

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

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

		list = new ArrayList<>();
		visited = new boolean[n + 1];
		result = new int[n + 1];

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

		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 money = Integer.parseInt(st.nextToken());
			list.get(start).add(new City(end, money));
		}

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

		bfs(start, end);

		System.out.println(result[end]);
	}

	private static void bfs(int start, int end) {
		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});
		queue.add(new int[] { start, 0 });
		visited[start] = true;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			if (result[temp[0]] < temp[1])
				continue;
			for (int i = 0; i < list.get(temp[0]).size(); i++) {
				City city = list.get(temp[0]).get(i);
				if (!visited[city.num] || result[city.num] > temp[1] + city.money) {
					visited[city.num] = true;
					result[city.num] = temp[1] + city.money;
					queue.add(new int[] { city.num, result[city.num] });
				}
			}
		}
	}
}

 

Main

변수)
City : 도시 번호, 비용
n : 도시 개수
m : 버스 개수
list : 도시 연결된 버스
visited : 방문 여부
result : 최소 비용
start, end, money : 시작 도시, 도착 도시, 비용
queue : 우선순위 큐 <도시 번호, 비용>

 

도시 개수(n), 버스 개수(m)를 입력받는다. 버스 정보를 입력받은 후 list에 도시 번호와 비용을 저장해 둔다. 출발점의 번호와 도착점의 도시 번호를 입력받은 후 bfs 함수를 호출한다.

 

우선순위 큐를 사용해서 출발 도시 번호와 비용을 저장하며 방문 표시한다. queue가 빌 때까지 반복하며 현재 비용이 현재 도시까지의 비용보다 크다면 계산할 필요 없으므로 넘어간다. 현재 비용이 현재 도시 비용과 같거나 작다면 도시와 연결된 버스를 순환한다. 아직 방문하지 않았거나 최소 비용이라면 값을 업데이트해 준 후 queue에 추가해 준다.

 

최소 비용을 출력한다.

---

---