[BaekJoon] 1916 최소비용 구하기

1.  문제 링크

https://www.acmicpc.net/problem/1916

2.  문제

요약

• N개의 도시가 있고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있습니다.
• A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 도시의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 버스의 개수 M이 주어지며 세 번째 줄부터 M개의 줄에는 출발 도시의 번호, 도착지의 도시 번호, 버스 비용들이 주어집니다. M + 3번째 줄에는 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어집니다.
  • 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어집니다.
• 출력: 첫 번째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력합니다..

3.  소스코드

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

public class Main {
	HashMap<Integer, ArrayList<Edge>> map;
	public HashMap<Integer, Integer> dijkstra(int start) {
		HashMap<Integer, Integer> distances = new HashMap<Integer, Integer>();
		PriorityQueue<Edge> pQueue = new PriorityQueue<Edge>();
		for(int key : map.keySet()) {
			distances.put(key, Integer.MAX_VALUE);
		}
		distances.put(start, 0);
		pQueue.add(new Edge(start, distances.get(start)));
		while(!pQueue.isEmpty()) {
			Edge cur_node = pQueue.poll();
			int cur_vertex = cur_node.vertex;
			int cur_distance = cur_node.distance;
			if(distances.get(cur_vertex) < cur_distance) {
				continue;
			}
			ArrayList<Edge> nodeList = map.get(cur_vertex);
			for(int i = 0; i < nodeList.size(); i++) {
				Edge adjacentNode = nodeList.get(i);
				int adjacent = adjacentNode.vertex;
				int weight = adjacentNode.distance;
				int distance = weight + cur_distance;
				
				if(distance < distances.get(adjacent)) {
					distances.put(adjacent, distance);
					pQueue.add(new Edge(adjacent, distance));
				}
			}
		}
		return distances;
	}
	
	public void makeMap(int city_num, int[] starts, int[] ends, int[] weights) {
		map = new HashMap<>();
		for(int i = 1; i <= city_num; i++) {
			map.put(i, new ArrayList<Edge>());
		}
		for(int i = 0; i < starts.length; i++) {
			ArrayList<Edge> list = map.get(starts[i]);
			list.add(new Edge(ends[i], weights[i]));
			map.put(starts[i], list);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int city_num = Integer.parseInt(br.readLine());
		int bus_num = Integer.parseInt(br.readLine());
		int[] starts = new int[bus_num];
		int[] ends = new int[bus_num];
		int[] weights = new int[bus_num];
		String[] input;
		for(int i = 0; i < bus_num; i++) {
			input = br.readLine().split(" ");
			starts[i] = Integer.parseInt(input[0]);
			ends[i] = Integer.parseInt(input[1]);
			weights[i] = Integer.parseInt(input[2]);
		}
		input = br.readLine().split(" ");
		int start = Integer.parseInt(input[0]);
		int end = Integer.parseInt(input[1]);
		br.close();
		Main m = new Main();
		m.makeMap(city_num, starts, ends, weights);
		HashMap<Integer, Integer> distances = m.dijkstra(start);
		bw.write(distances.get(end) + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Edge implements Comparable<Edge> {
		int vertex;
		int distance;
		public Edge(int vertex, int distance) {
			this.vertex = vertex;
			this.distance = distance;
		}
		@Override
		public int compareTo(Edge e) {
			// TODO Auto-generated method stub
			return this.distance - e.distance;
		}
		
	}
}

4.  접근

• 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있습니다.

다익스트라(Dijkstra) 알고리즘

• 다익스트라 알고리즘은 최단 경로를 탐색하는 알고리즘입니다.
• 간선에 비용이 있는 가중치 그래프에서 사용하고, 특정 노드에서 각각의 노드들에 갈 수 있는 최단 경로를 찾습니다.

실행 순서

• 시작 노드를 설정하고 시작 노드에서 각 노드들에 갈 수 있는 최단 거리를 나타내는 배열을 생성하며 값을 초기화합니다.
• 시작 노드에서부터 시작해서 현재 위치해있는 노드에 연결되어 있는 노드들로의 최단 거리를 계산합니다.
• 연결된 노드로의 현재 거리와 현재 위치해있는 노드에서 연결된 노드로 가는 거리를 비교하여 현재 거리가 더 크다면 현재 위치해있는 노드에서 연결된 노드로 가는 거리로 변경합니다.
• 위 과정을 반복하면 결과적으로 가중치의 합이 가장 적은 값들이 들어가게 되어 시작 노드에서부터 각각의 노드들 간의 최단 거리를 구할 수 있습니다.
  
  

풀이

• 출발 도시를 입력 받아서 출발 도시부터 다른 도시로의 최소 비용을 구하는 다익스트라 알고리즘을 이용하여 다른 도시들로의 최소 비용을 구하고 그 때의 도착 도시까지의 비용을 출력하면 되는 문제입니다.

1. 특정 도시에서 연결된 다른 도시들로의 비용을 나타내는 HashMap을 생성하고 해당 정보들을 HashMap에 넣어줍니다.
2. 다익스트라 알고리즘을 이용하여 출발 도시부터 다른 도시들로의 최소 비용을 구합니다.
   1. 출발 도시로부터 다른 도시들로의 최소 비용을 나타내는 HashMap을 생성하고 방문할 도시들을 나타내는 거리를 기준으로 가중치를 매긴 PriorityQueue를 생성합니다.
   2. HashMap의 값들을 int형의 최댓값으로 초기화시키고 출발 도시의 HashMap 값을 0으로 초기화시킵니다.
   3. 출발 도시 및 출발 도시의 HashMap 값을 PriorityQueue에 넣어줍니다.
   4. PriorityQueue가 비워지기 전까지 반복문을 돌면서 출발 도시부터 다른 도시들로의 최소 비용을 구합니다.
      1. PriorityQueue에서 우선순위가 가장 높은 도시 및 현재까지의 최소 비용을 뽑아냅니다.
      2. 현재 위치한 도시의 현재까지의 최소 비용이 현재 위치한 도시의 HashMap 값보다 크다면 다음 PriorityQueue의 도시로 넘어갑니다.
      3. 그렇지 않다면 현재 위치한 도시와 연결된 도시들을 nodeList라는 ArrayList에 담습니다.
      4. nodeList에 있는 모든 도시들을 돌면서 최소 비용을 구합니다.
         1. 현재 위치한 도시의 현재까지의 최소 비용과 현재 nodeList에 있는 도시까지의 비용을 더하여 비용을 계산한 후 해당 비용이 현재 nodeList에 있는 도시의 HashMap 값보다 작다면 해당 비용으로 HashMap 값을 변경하고 PriorityQueue에 현재 nodeList에 있는 도시 및 해당 비용을 넣어줍니다.
3. 2번 과정이 끝난 후에 HashMap에서 도착 도시까지의 비용을 출력합니다.