[백준/Java] 1753 최단경로

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

문제 요약

V개의 정점과 E개의 간선으로 구성된 방향 그래프가 주어질 때, 주어진 시작 정점 K에서 다른 모든 정점으로의 최단 경로를 구하여라.

각 정점에는 1부터 V까지의 번호가 매겨져 있다.
두 정점 간에는 여러 개의 간선이 존재할 수도 있다.
시작점 자신과의 거리는 0으로 출력하며, 경로가 존재하지 않는 경우에는 INF를 출력한다.

정점의 개수 V는 최대 2만이다.
간선의 개수 E는 최대 30만이다.
각 간선의 정보는 시작 정점 u, 도착 정점 v, 가중치 w의 순서로 주어지며, w는 10 이하의 자연수이다.

---

문제 접근

전형적으로 다익스트라 문제를 사용하여 해결할 수 있는 문제이다.

주의할 점은 두 정점 간에 여러 개의 간선이 존재할 수도 있다는 것인데, 사실 우선순위 큐를 이용해서 다음 방문 정점을 선택한다면 이것도 크게 고려할 필요는 없다.

다익스트라를 하다보면 고민되는 점은 방문 여부를 언제 기록하고 언제 확인할 지인데, 왠지 방문 여부를 미리 기록하면 좋을 것 같지만, 그러면 마지막 간선의 영향을 무시하게 되기 때문에 그냥 현재 탐색하는 정점에서 확인하고 기록하는 것이 맞다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (추가 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	static int INF = 1000000;
	
	static int V, E;
	static int startPoint;
	static ArrayList<int[]>[] graph;
	static int[] distance;
	
	// 입력 받기
	public static void getInput() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// V, E 입력 받기
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st1.nextToken());
		E = Integer.parseInt(st1.nextToken());
		
		// 시작점 입력 받기
		startPoint = Integer.parseInt(br.readLine());
		
		// 그래프 초기화
		graph = new ArrayList[V+1];
		for (int i = 1; i < V+1; i++) {
			graph[i] = new ArrayList<>();
		}

		// 그래프 입력 받기
		for (int i = 0; i < E; i++) {
			StringTokenizer stE = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(stE.nextToken());
			int v = Integer.parseInt(stE.nextToken());
			int w = Integer.parseInt(stE.nextToken());
			
			int[] nextVertex = new int[] {v, w};
			
			graph[u].add(nextVertex);
		}
	}
	
	// 다익스트라 알고리즘을 이용해 최단 거리 찾기
	public static void findPath() {
		// 거리의 오름차순으로 정렬되는 우선순위 큐 선언
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		// 방문 여부를 판단하는 배열 선언 및 초기화
		boolean[] visited = new boolean[V+1];
		for (int i = 0; i < V+1; i++) {
			visited[i] = false;
		}
		
		// 최단 거리 배열 초기화
		distance = new int[V+1];
		for (int i = 0; i < V+1; i++) {
			distance[i] = INF;
		}
		
        // 시작점의 거리 설정, 큐에 넣음
        distance[startPoint] = 0;
        int[] start = new int[] {startPoint, 0};
        pq.add(start);
		
		while (pq.size() > 0) {
			// 현재 시작점과 가장 가까운 정점을 꺼낸다.
			int[] now = pq.poll();
			// 갱신되는 것도 모두 큐에 넣기 때문에 이미 방문한 것들은 다시 보지 않도록 설정
			if (visited[now[0]]) continue;
			// 방문 기록 남김
			visited[now[0]] = true;
			
			// 현 정점에서 도달할 수 있는 모든 정점 확인
			for (int[] next : graph[now[0]]) {
				// 이미 방문한 정점이라면 넘어감
				if (visited[next[0]]) continue;
				// 거리 재설정
				distance[next[0]] = Math.min(distance[next[0]], distance[now[0]] + next[1]);
				// 우선순위 큐에 넣음
				int[] updatedNext = new int[] {next[0], distance[next[0]]};
				pq.add(updatedNext);
			}
		}
	}
	
	// 정답 생성 및 출력
	public static void printAnswer() {
		StringBuilder sb = new StringBuilder();
		
		// 거리 배열을 사용해 정답 구성
		for (int i = 1; i < V+1; i++) {
			if (distance[i] == INF) sb.append("INF\n");
			else sb.append(distance[i]+"\n");
		}
		
		// 정답 출력
		System.out.println(sb);
	}
	
	public static void main(String[] args) throws IOException {
		// 입력 받기
		getInput();
		
		// 다익스트라 알고리즘을 이용해 최단 거리 찾기
		findPath();
		
		// 정답 생성 및 출력
		printAnswer();
	}
}

---

회고

생각보다 실수를 많이 했다. 사실 풀었던 순서의 반대로 글을 작성하고 있기 때문에 실수를 더 많이하는게 일반적이긴 하다.

틀렸던 이유 1
현재 방문 중인 정점에서 방문 여부를 확인하지 않아 메모리 초과가 발생했다.

틀렸던 이유 2
다익스트라를 제대로 사용하지 않고, 첫번째 정점에서 도달할 수 있는 정점들의 거리를 미리 구했다.
사실 이걸 미리 구하는 것 자체는 틀릴 이유는 아닌데, 두 정점 간에 여러 개의 간선이 존재할 수도 있다는 점을 간과해서 틀렸다.