[백준/1916] 최소비용 구하기 (Java)

지니·2021년 6월 16일
0

Algorithm_BFS

목록 보기
14/15

Question


문제 해설

  1. N개의 도시 존재
  2. 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스 존재
  3. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용은?
  4. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수



Solution

풀이 접근 방법

  1. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용
    1. 하나의 시작점 -> 다수의 도착지점까지의 최단 거리 => 다익스트라 / 벨만포드 알고리즘
    2. A부터 모든 노드까지의 최단 거리를 구하고, 거기서 B의 값 리턴
  2. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수 -> 음수 없음
    1. => 다익스트라 알고리즘 사용

정답 코드

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.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Bus implements Comparable<Bus> {
	int end, weight;

	public Bus(int end, int cost) {
		this.end = end;
		this.weight = cost;
	}

	@Override
	public int compareTo(Bus o) {
		return Integer.compare(this.weight, o.weight);
	}

}

public class Main {
	static int N;
	static ArrayList<Bus>[] busInfo;

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

		N = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		busInfo = new ArrayList[N + 1];

		// 각 도시마다 다음 도시의 정보를 담은 연결 리스트 배열 초기화
		for (int i = 0; i < busInfo.length; i++) {
			busInfo[i] = new ArrayList<Bus>();
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int s = Integer.valueOf(st.nextToken());
			int e = Integer.valueOf(st.nextToken());
			int cost = Integer.valueOf(st.nextToken());

			busInfo[s].add(new Bus(e, cost));
		}

		st = new StringTokenizer(br.readLine());

		int start = Integer.valueOf(st.nextToken());
		int end = Integer.valueOf(st.nextToken());
		int minCost = find(start, end);

		bw.write(minCost + "\n");
		bw.flush();
		bw.close();
	}

	public static int find(int start, int end) {
		int[] dist = new int[N + 1];

		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;

		// 이동 버스 비용을 오른차순 기준 정렬
		// 낮은 값을 가지는 도시부터 선택
		PriorityQueue<Bus> pq = new PriorityQueue<Bus>();
		pq.add(new Bus(start, 0));

		while (!pq.isEmpty()) {
			Bus current = pq.poll();

			if (current.weight > dist[current.end])
				continue;

			// 해당 도시에서 이동할 수 있는 도시들 탐색
			for (Bus next : busInfo[current.end]) {
				int nextEnd = next.end;
				int newWeight = dist[current.end] + next.weight;

				// 현재까지의 비용 + 이동 비용 < 이동할 노드의 비용
				if (newWeight < dist[nextEnd]) {
					dist[nextEnd] = newWeight;
					pq.add(new Bus(nextEnd, newWeight));
				}
			}

		}

		return dist[end];
	}
}

profile
코.빠.죄.아 (코딩에 빠진 게 죄는 아니잖아..!)

0개의 댓글