[BOJ] 1753. 최단경로

문제 주소: 클릭

1753번: 최단경로

OOO맵아 용산역에서 서울 고속버스 터미널까지 가장 빨리 가는 방법을 알려줘!

위의 사진은 지도어플의 벡터 지도 일부를 캡처한 모습입니다. 

 

용산역에서 서울 고속버스 터미널을 가고싶을 때, 우리는 일반적으로

출발지점을 용산역,

도착지점을 터미널로 두고 검색을 하게 됩니다

 

이 때, 용산역에서 버스 터미널로 한 방에 갈 수 있는 거리가 가장 빠를 때도 있지만,

간혹, 다른 구역을 거쳐서 가면 한 번에 가는 것보다 더 빠르게 갈 수 있을 때도 있죠?

 

이처럼 A에서 B로 갈 때 다른 지점들을 거쳐서 최대한 빨리 갈 수 있는 길을 알려주는 알고리즘이 바로 다익스트라의 최단거리 알고리즘입니다.

 

다익스트라 알고리즘을 구현하는 방법은 다음과 같이 크게 2가지가 있습니다.

A와 B를 정점이라고 했을 때,

1). 2차원 인접행렬: A -> B로 가는 거리를 저장한 2차원 배열

2).  인 접 리 스 트: A -> B로 갈 수 있는 정점과 그 거리를 갖는 객체를 리스트화 한 것

 

그런데 여기서 주의할 점이 있습니다.

 

인접행렬의 자료형이 int 이면서,

정점의 개수가 2만개만 되도 2*10^4 * 2*10^4으로 총 4*10^8로 4억개의 int 가 필요합니다.

int 하나는 4byte이고 4*4*10^8 byte = 16억 바이트. 

 

계산기로 계산해보니 총 1.5기가의 메모리가 필요하게 됩니다.

 

따라서 이 문제에서는 인접리스트를 사용하여 필요한 정점들만 사용할 필요가 있습니다.

 

그리고 다익스트라 알고리즘의 작동방식은 다음과 같습니다.

 

1. 시작 지점을 정하고 각 지점에서 다른 지점까지 걸리는 거리를 인접리스트에 저장한다.

   이 때, 갈 수 없는 길에는 무한대(아주 큰 값, JAVA의 경우 Integer.MAX_VALUE)를 저장한다.

2. 시작지점에서 목적지(Second)로 한 번에 가는 길과

시작지점과 목적지 사이에 다른 지점을 거쳐가는 경우를 비교하여 더 적게 걸리는 지점을 최단거리로 갱신한다. 

3. 최단거리가 구해지면 결과를 출력한다.

 

곧 유튜브를 통해 강의가 올라올 예정입니다.

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

public class Main최단경로 {
	private static class Edge implements Comparable {
		int num, cost;

		public Edge(int v, int dist) {
			this.num = v;
			this.cost = dist;
		}

		public int compareTo(Edge o) {
			return cost - o.cost;
		}
	}

	private static final int INF = Integer.MAX_VALUE;
	private static int V, E, start;

	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());

		ArrayList[] adjList = new ArrayList[V + 1]; // 정점번호는 1~2만
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			if (adjList[a] == null)
				adjList[a] = new ArrayList<>();
			// 간선 정보 집어넣기
			adjList[a].add(new Edge(b, dist));
		}

		// 못 가는 정점들이 있을 수 있으므로 초기값은 모두 무한대를 저장한다.
		int[] dist = new int[V + 1];
		boolean[] visit = new boolean[V + 1];

		// 큐: 큐에는 새롭게 갱신 된 점과 단축된 거리가 들어갑니다.
		PriorityQueue q = new PriorityQueue<>();
		for (int i = 1; i <= V; i++) {
			dist[i] = INF;
		}

		q.add(new Edge(start, 0)); // 시작점부터 출발, 자기자신과의 거리는 0
		dist[start] = 0;
		while (!q.isEmpty()) {
			Edge b = q.poll();

			// 방문 검사
			if (visit[b.num])
				continue;
			visit[b.num] = true;

			// 들어온 정점과 연결된게 없을 수도 있다.
			if (adjList[b.num] == null)
				continue;
			for (Edge c : adjList[b.num]) {
				int newDist = dist[b.num] + c.cost;
				// 갱신할 수 있는 거리는 갈 수 있을 때까지 더 가봐야 하기 때문에 큐에 넣어준다.
				if (dist[c.num] > newDist) {
					dist[c.num] = newDist;
					q.add(new Edge(c.num, dist[c.num]));
				}
			}
		}

		// 시작점으로 부터 떨어진 거리 출력
		for (int i = 1; i <= V; i++) {
			sb.append(dist[i] == INF ? "INF" : dist[i]).append("\n");
		}
		System.out.println(sb);
	}
}