https://www.acmicpc.net/problem/1504
문제 요약
양방향 그래프가 주어질 때, 1번 정점에서 N번 정점으로 가는 최단 거리를 구하려고 한다.
이때, 임의로 주어진 두 정점을 반드시 통과해야 한다는 제약이 있다.
한번 이동했던 정점, 간선을 다시 이용해도 된다.
정점의 개수 N은 최대 800이다.
간선의 개수 E는 최대 20만이다.
도로의 정보는 두 정점과 길이로 주어지며, 이는 양방향 도로를 의미한다.
반드시 거쳐야 하는 두 개의 서로 다른 정점 v1과 v2가 주어진다.
이때 두 개의 정점을 지나면서 1번 노드에서 N번 노드에 도달하는 최단 경로의 길이를 구하여라.
그러한 경로가 없다면 -1을 출력한다.
문제 접근
이 문제는 결국 시작 정점(1번 노드)에서 출발하여, 중간에 두 정점(v1, v2)을 거치고, 마지막에 도착 정점(N번 노드)에 도달하는 것이 목표이다.
이를 고려하면 다익스트라 알고리즘을 여러 번 사용하면 되는 문제로 보인다.
이때 유의할 점은 중간에 두 정점을 거친다고 했지만, 어떤 순서로 거치라는 말은 없었다는 것이다.
즉, (1 → v1) + (v1 → v2) + (v2 → N)으로 얻어지는 거리와 (1 → v2) + (v2 → v1) + (v1 → N)으로 얻어지는 거리 중 더 작은 값이 정답이 될 것이다.
이때 그래프는 양방향이므로 (v1 → v2)와 (v2 → v1)의 거리는 같기 때문에 다익스트라를 5번 사용하면 문제를 해결할 수 있다.
풀이
기본적인 아이디어는 다음과 같다.
- 인접 리스트의 형태로 양방향 그래프를 구성한다.
- 다익스트라 알고리즘을 5번 사용하여 필요한 값을 모두 구한다.
- 가능한 두 가지 경로의 거리를 비교하여 정답을 얻는다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int N, E, V1, V2;
static ArrayList<int[]>[] graph;
static final int MAX_VALUE = 100000000;
// 다익스트라로 최단 거리를 구하는 함수
public static int dijkstra(int start, int end) {
// 거리 오름차순의 우선순위 큐
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[N+1];
int[] distance = new int[N+1];
for (int i = 0; i < N+1; i++) {
visited[i] = false;
distance[i] = MAX_VALUE;
}
// 시작점을 우선순위 큐에 넣고 다익스트라 시작
int[] initial = new int[]{start, 0};
pq.add(initial);
distance[start] = 0;
while (!pq.isEmpty()) {
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]], now[1]+next[1]);
int[] newNext = new int[]{next[0], distance[next[0]]};
pq.add(newNext);
}
}
return distance[end];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N, E 입력 받기
StringTokenizer st1 = new StringTokenizer(br.readLine());
N = Integer.parseInt(st1.nextToken());
E = Integer.parseInt(st1.nextToken());
// 그래프 선언
// 정점 번호가 1부터 시작하기 때문에 N+1 크기로 선언
graph = new ArrayList[N+1];
for (int i = 0; i < N+1; i++) {
graph[i] = new ArrayList<>();
}
// 그래프 입력 받기
for (int i = 0; i < E; i++) {
StringTokenizer stE = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stE.nextToken());
int b = Integer.parseInt(stE.nextToken());
int c = Integer.parseInt(stE.nextToken());
// 양방향 그래프이므로 양 쪽 모두 추가해야 한다.
int[] forward = new int[]{b, c};
int[] backward = new int[]{a, c};
graph[a].add(forward);
graph[b].add(backward);
}
// 두 정점 입력 받기
StringTokenizer st2 = new StringTokenizer(br.readLine());
V1 = Integer.parseInt(st2.nextToken());
V2 = Integer.parseInt(st2.nextToken());
// 다익스트라 함수를 이용해 가능한 두가지 경우의 거리 구하기
// 중복 정점이 가능하기 때문에 이렇게 계산해도 된다. 또는 해야 된다.
int first = 0;
int second = 0;
int distVs = dijkstra(V1, V2);
first = dijkstra(1, V1) + distVs + dijkstra(V2, N);
second = dijkstra(1, V2) + distVs + dijkstra(V1, N);
// 두 값 중 최소인 값이 정답이다.
int answer = Math.min(first, second);
if (answer >= MAX_VALUE) answer = -1; // 경로가 존재하지 않는 경우 -1을 출력한다.
System.out.println(answer);
}
}회고
틀렸던 이유 1
그래프가 양방향인데, 단방향으로만 간선을 추가했다. 그리고 경로가 없는 경우에 -1을 출력하는 예외처리도 하지 않았다.
틀렸던 이유 2
다익스트라 알고리즘을 잘못 구현했다. 방문 여부 확인 및 기록을 현재 탐색 중인 노드에서 수행해야 한다. 만약 다음 노드를 훑을 때 방문 여부를 기록하면 마지막에 엄청 큰 가중치가 추가되어도 이미 방문 여부가 기록되어 다른 경로로 이를 갱신해주지 못한다.
