[BOJ/Java] 1753. 최단경로

[BOJ/Java] 1753. 최단경로

1753번: 최단경로

---

문제 해석

이 문제는 주어진 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 고전적인 다익스트라 알고리즘 문제다. 주어진 그래프는 방향성이 있으며, 각 간선에는 가중치가 존재한다.

풀이 과정

제출된 코드는 다음 단계로 문제를 해결한다:

 

1. 입력 받기: 각 간선 정보를 입력받아 인접 리스트에 저장한다.
2. 다익스트라 알고리즘 실행: 우선순위 큐를 사용하여 현재 정점에서 가장 짧은 거리에 있는 정점을 우선적으로 처리한다. 이를 통해, 다른 모든 정점까지의 최단 거리를 계산한다.
3. 결과 출력: 계산된 최단 거리를 출력하며, 도달할 수 없는 경우 'INF'를 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No1753;

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;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().sol();
	}

	private int V; // 정점의 수
	private int E; // 간선의 수
	private int K; // 시작 정점
	private ArrayList<ArrayList<Vertex>> graph; // 그래프를 표현할 인접 리스트
	private StringBuilder sb = new StringBuilder(); // 결과를 담을 StringBuilder

	private void sol() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine()) - 1; // 0-based index로 조정

		// 그래프 초기화
		graph = new ArrayList<>();
		for (int i = 0; i < V; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 간선 정보 입력
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken()) - 1;
			int v2 = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());
			graph.get(v1).add(new Vertex(v2, w));
		}
		
		dijkstra(); // 다익스트라 알고리즘 실행
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	private void dijkstra() {
		int[] d = new int[V];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[K] = 0; // 시작점의 최단 경로 비용은 0
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>(); // 최소 힙 구조
		pq.offer(new Vertex(K, d[K]));
		
		while(!pq.isEmpty()) {
			Vertex cur = pq.poll(); // 가장 짧은 거리의 정점 선택
			
			if(cur.w > d[cur.v]) continue; // 이미 처리된 정점은 스킵
			
			for (Vertex next : graph.get(cur.v)) {
				if(cur.w + next.w < d[next.v]) { // 더 짧은 경로를 찾은 경우
					d[next.v] = cur.w + next.w;
					pq.offer(new Vertex(next.v, d[next.v]));
				}
			}
		}
		
		// 결과 저장
		for (int i = 0; i < V; i++) {
			if(d[i] == Integer.MAX_VALUE) sb.append("INF\n");
			else sb.append(d[i]).append("\n");
			}
	}
	
	class Vertex implements Comparable<Vertex>{
		int v, w; // 정점과 가중치

		public Vertex(int v, int w) {
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Vertex o) { // 우선순위 큐를 위한 비교 기준
			return this.w - o.w;
		}
	}
}

시간 복잡도 분석

다익스트라 알고리즘의 시간 복잡도는 𝑂((𝑉+𝐸)log⁡𝑉)이다. 여기서 𝑉V는 정점의 수, 𝐸는 간선의 수이다. 우선순위 큐를 사용함으로써 각 정점과 간선을 효율적으로 처리한다.

느낀점

이 문제를 통해 그래프의 최단 경로를 찾는 다익스트라 알고리즘을 실제로 구현해보며, 특히 우선순위 큐를 활용하여 효율적인 알고리즘 설계의 중요성을 다시 한번 인식하였다. 이와 같은 알고리즘은 다양한 실제 문제 해결에 유용하게 적용될 수 있다.