BEAKJOON / 백준 - JAVA 1916번 최소비용 구하기

2024.09.06기준 - 골드5

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 버스의 간선들을 알려줄 때 시작 도시와 도착 도시에 최단 경로를 출력하는 문제입니다.

 

다익스트라

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.

이 알고리즘은 음의 가중치를 가지지 않는 그래프에서만 작동합니다.

 

작동 원리

1. 시작 노드 설정
   • 시작 노드의 거리를 0으로 설정하고, 나머지 노드의 거리를 무한대로 설정합니다.
2. 우선순위 큐 초기화
   • 시작 노드를 우선순위 큐에 추가합니다.
3. 최단 거리 노드 선택
   • 우선순위 큐에서 가장 작은 거리를 가진 노드를 선택합니다.
4. 거리 업데이트
   • 선택된 노드를 통해 인접한 노드로 가는 거리가 더 짧다면, 그 거리를 업데이트하고 우선순위 큐에 추가합니다.
5. 반복
   • 모든 노드가 처리될 때까지 3번과 4번 단계를 반복합니다.

우선순위 큐를 사용하는 이유

다익스트라 알고리즘에서 우선순위 큐(Priority Queue)를 사용하는 이유는 효율성을 높이기 위해서입니다. 우선순위 큐를 사용하면 최소 거리를 가진 노드를 빠르게 찾을 수 있어, 알고리즘의 시간 복잡도를 크게 줄일 수 있습니다. 기본적인 다익스트라 알고리즘의 시간 복잡도는 O(N^2)이지만, 우선순위 큐를 사용하면 O(E log N)으로 개선됩니다.

(E는 간선의 수, N은 노드의 수)

1. 버스가 도착하는 위치와 비용을 저장하는 클래스를 생성합니다.

Comparable을 상속받아 우선순위 큐를 사용할 수 있게 해줍니다.(정렬이 필요하기 때문입니다.)

// 버스가 도착하는 위치와, 비용을 저장하는 클래스.
public static class Node implements Comparable<Node> {
    int end, price;

    public Node(int e, int p) {
        end = e;
        price = p;
    }

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

 

2. 입력받은 정보와 방문 여부, 거리 최솟값을 저장하는 배열과 변수들을 미리 셋팅을 해주었습니다.

// 시작하는 위치와 도착하는 위치, 비용을 저장하는 map
map = new LinkedHashMap<>();
visit = new boolean[n + 1]; // 방문 여부를 저장하는 배열

// 각 위치에서 최솟 값을 저장하는 배열
dis = new int[n + 1];

// 최솟값을 저장하기 위해 MAX값으로 기본 설정.
Arrays.fill(dis, Integer.MAX_VALUE);

 

3. 저는 Map을 이용해 시작하는 도시를 키를 잡고 갈 수 있는 도시를 value로 잡아 진행했습니다.

StringTokenizer st;
int start, end, price;
for (int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken()); // 시작 버스
    end = Integer.parseInt(st.nextToken()); // 도착 버스
    price = Integer.parseInt(st.nextToken()); // 비용

    // map에 start키가 업다면 list를 생성해준다.
    if (!map.containsKey(start)) {
        map.put(start, new ArrayList<>());
    }

    map.get(start).add(new Node(end, price));
}

 

4. 추가로 시작하는 도시와 도착하는 도시를 입력받아 함수를 호출해줍니다.

st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken()); // 시작 버스
end = Integer.parseInt(st.nextToken()); // 도착 버스

// 함수 호출
function(start);

 

5. 다익스트라 함수 호출

위에서 설명했듯이 우선순위 큐를 사용하는 이유는 시간복잡도 개선과 노드 선택을 효율적으로 하기 위해 선언해줍니다.

// 최소 거리 노드 선택을 효율적으로 수행하기 위해 PriorityQueue 사용.
// 매 반복마다 모든 노드를 확인을 하지 않기 위해 사용.
// 기본적인 다익스트라 알고리즘은 O(N^2) 시간복잡도를 가지지만 우선순위 큐를 사용하면 O(E logN)으로 개선 가능.
// E 간선의 수, N 노드의 수
PriorityQueue<Node> q = new PriorityQueue<>();

 

초기 시작 도시 위치와 비용을 0으로 설정해 추가해줍니다.

// 시작 버스 위치인 s와 비용 0을 저장.
q.add(new Node(s, 0));

// 시작 위치는 0
dis[s] = 0;

 

반복문에서 방문하지 않은 도시라면 조건문으로 들어가게 해주고 방문 처리 표시를 해줍니다.

조건문에서는 방문한 도시에 갈 수 있는 도시들을 전부 확인해주며

방문하지 않았고, 계산된 거리가 현재 배열에 저장된 거리보다 짧다면 추가로 큐에 들어가게 만들어줍니다.

Node node;
while (!q.isEmpty()) {
    node = q.poll();

    // 방문하지 않은 곳이라면
    if (!visit[node.end]) {
        visit[node.end] = true; // 방문 체크

        // 방문한 곳에서 갈 수 있는 곳이 없다면
        if (!map.containsKey(node.end)) {
            continue;
        }

        for (Node nd : map.get(node.end)) {
            // 방문하지않고 거리가 계산된 거리보다 작다면 조건문 안으로 들어간다.
            if (!visit[nd.end] && dis[node.end] + nd.price < dis[nd.end]) {
                dis[nd.end] = dis[node.end] + nd.price;
                q.add(new Node(nd.end, dis[nd.end]));
            }
        }
    }
}

 

6. 해당하는 도착 도시의 거리를 출력해줍니다.

bw.write(Integer.toString(dis[end]));
bw.flush();
bw.close();
br.close();

 

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	// 버스가 도착하는 위치와, 비용을 저장하는 클래스.
	public static class Node implements Comparable<Node> {
		int end, price;
		
		public Node(int e, int p) {
			end = e;
			price = p;
		}
		
		@Override
		public int compareTo(Node o) {
			return price - o.price;
		}
	}
	
	static int n, m;
	static Map<Integer, List<Node>> map;
	static int[] dis;
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine()); // 도시의 개수
		m = Integer.parseInt(br.readLine()); // 버스의 개수
		
		// 시작하는 위치와 도착하는 위치, 비용을 저장하는 map
		map = new LinkedHashMap<>();
		visit = new boolean[n + 1]; // 방문 여부를 저장하는 배열
		
		// 각 위치에서 최솟 값을 저장하는 배열
		dis = new int[n + 1];
		
		// 최솟값을 저장하기 위해 MAX값으로 기본 설정.
		Arrays.fill(dis, Integer.MAX_VALUE);
		
		StringTokenizer st;
		int start, end, price;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken()); // 시작 버스
			end = Integer.parseInt(st.nextToken()); // 도착 버스
			price = Integer.parseInt(st.nextToken()); // 비용
			
			// map에 start키가 업다면 list를 생성해준다.
			if (!map.containsKey(start)) {
				map.put(start, new ArrayList<>());
			}
			
			map.get(start).add(new Node(end, price));
		}
		
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken()); // 시작 버스
		end = Integer.parseInt(st.nextToken()); // 도착 버스
		
		// 함수 호출
		function(start);
		
		bw.write(Integer.toString(dis[end]));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static void function(int s) {
		// 최소 거리 노드 선택을 효율적으로 수행하기 위해 PriorityQueue 사용.
		// 매 반복마다 모든 노드를 확인을 하지 않기 위해 사용.
		// 기본적인 다익스트라 알고리즘은 O(N^2) 시간복잡도를 가지지만 우선순위 큐를 사용하면 O(E logN)으로 개선 가능.
		// E 간선의 수, N 노드의 수
		PriorityQueue<Node> q = new PriorityQueue<>();
		
		// 시작 버스 위치인 s와 비용 0을 저장.
		q.add(new Node(s, 0));
		
		// 시작 위치는 0
		dis[s] = 0;
		
		Node node;
		while (!q.isEmpty()) {
			node = q.poll();
			
			// 방문하지 않은 곳이라면
			if (!visit[node.end]) {
				visit[node.end] = true; // 방문 체크
				
				// 방문한 곳에서 갈 수 있는 곳이 없다면
				if (!map.containsKey(node.end)) {
					continue;
				}
				
				for (Node nd : map.get(node.end)) {
					// 방문하지않고 거리가 계산된 거리보다 작다면 조건문 안으로 들어간다.
					if (!visit[nd.end] && dis[node.end] + nd.price < dis[nd.end]) {
						dis[nd.end] = dis[node.end] + nd.price;
						q.add(new Node(nd.end, dis[nd.end]));
					}
				}
			}
		}
	}
}