1. 문제 링크
https://www.acmicpc.net/problem/1504
2. 문제
요약
- 방향성이 없는 그래프가 주어지고 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 합니다.
- 1번 정점에서 N번 정점까지의 특정한 최단 경로를 구하는데 임의로 주어진 두 정점을 반드시 통과하는 최단 경로를 구하려고 합니다.
- 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 지나는 최단 경로의 길이를 구하는 문제입니다.
- 입력: 첫 번째 줄에 2보다 크거나 같고 800보다 작거나 같은 정점의 개수 N과 0보다 크거나 같고 200,000보다 작거나 같은 간선의 개수 E가 주어지고 두 번째 줄부터 E개의 줄에 세 정수 a, b, c가 주어지는데 이는 a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻입니다. 그 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 , 가 주어집니다.
- c는 1보다 크거나 같고 1,000보다 작거나 같으며 과 는 다르고 은 N일 수 없으며 는 1이 될 수 없습니다.
- 두 정점 u와 v 사이에는 간선이 최대 1개 존재합니다.
- 출력: 첫 번째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력합니다. 만약 그러한 경로가 없다면 -1을 출력합니다.
3. 소스코드
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.HashMap;
import java.util.PriorityQueue;
public class Main {
static HashMap<Integer, ArrayList<Edge>> map;
public HashMap<Integer, Integer> dijkstra(int start) {
HashMap<Integer, Integer> distances = new HashMap<>();
PriorityQueue<Edge> queue = new PriorityQueue<>();
for(int key : map.keySet()) {
distances.put(key, Integer.MAX_VALUE);
}
distances.put(start, 0);
queue.add(new Edge(start, distances.get(start)));
while(!queue.isEmpty()) {
Edge cur_node = queue.poll();
int cur_vertex = cur_node.vertex;
int cur_weight = cur_node.weight;
if(distances.get(cur_vertex) < cur_weight) {
continue;
}
ArrayList<Edge> nodeList = map.get(cur_vertex);
for(int i = 0; i < nodeList.size(); i++) {
Edge adjacentNode = nodeList.get(i);
int adjacent = adjacentNode.vertex;
int weight = adjacentNode.weight;
int distance = weight + cur_weight;
if(distance < distances.get(adjacent)) {
distances.put(adjacent, distance);
queue.add(new Edge(adjacent, distance));
}
}
}
return distances;
}
public int getMinWeight(int u, int v) {
HashMap<Integer, Integer> start = dijkstra(1);
HashMap<Integer, Integer> stopover1 = dijkstra(u);
HashMap<Integer, Integer> stopover2 = dijkstra(v);
int st1 = Integer.MAX_VALUE;
int st2 = Integer.MAX_VALUE;
if(start.get(u) != Integer.MAX_VALUE) {
if(stopover1.get(v) != Integer.MAX_VALUE) {
if(stopover2.get(map.size()) != Integer.MAX_VALUE) {
st1 = start.get(u) + stopover1.get(v) + stopover2.get(map.size());
}
}
}
if(start.get(v) != Integer.MAX_VALUE) {
if(stopover2.get(u) != Integer.MAX_VALUE) {
if(stopover1.get(map.size()) != Integer.MAX_VALUE) {
st2 = start.get(v) + stopover2.get(u) + stopover1.get(map.size());
}
}
}
if(st1 == Integer.MAX_VALUE && st2 == Integer.MAX_VALUE) {
return -1;
}
if(st1 > st2) {
return st2;
} else {
return st1;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
int vertex_num = Integer.parseInt(input[0]);
int edge_num = Integer.parseInt(input[1]);
map = new HashMap<>();
for(int i = 1; i <= vertex_num; i++) {
map.put(i, new ArrayList<Edge>());
}
for(int i = 0; i < edge_num; i++) {
input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
int weight = Integer.parseInt(input[2]);
ArrayList<Edge> edges = map.get(start);
edges.add(new Edge(end, weight));
map.put(start, edges);
edges = map.get(end);
edges.add(new Edge(start, weight));
map.put(end, edges);
}
input = br.readLine().split(" ");
int u = Integer.parseInt(input[0]);
int v = Integer.parseInt(input[1]);
br.close();
Main m = new Main();
bw.write(m.getMinWeight(u, v) + "\n");
bw.flush();
bw.close();
}
public static class Edge implements Comparable<Edge> {
int vertex, weight;
public Edge(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Edge e) {
// TODO Auto-generated method stub
return this.weight - e.weight;
}
}
}4. 접근
- 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있습니다.
- 1번 정점에서 주어진 두 개의 정점 u, v를 지나 N번 정점으로 가야 하므로 아래와 같이 2개의 경로가 발생될 수 있습니다.
- 1 -> u -> v -> N
- 1 -> v -> u -> N
- 그렇기 때문에 우선 1번 정점에서 다익스트라 알고리즘을 통해 각 정점까지의 최단 거리를 구하고 u번 정점에서 다익스트라 알고리즘을 통해 각 정점까지의 최단 거리를 구하며, v번 정점에서 다익스트라 알고리즘을 통해 각 정점까지의 최단 거리를 구합니다.
- 위 과정을 통해 1번, u번, v번 정점에서 시작했을 때의 최단 거리를 구해놨기 때문에 (1번 정점에서 u번 정점으로 가는 최단 거리 + u번 정점에서 v번 정점으로 가는 최단 거리 + v번 정점에서 N번 정점으로 가는 최단 거리)와 (1번 정점에서 v번 정점으로 가는 최단 거리 + v번 정점에서 u번 정점으로 가는 최단 거리 + u번 정점에서 N번 정점으로 가는 최단 거리)를 구할 수 있게 됩니다.
- 두 개의 경로에 대한 최단 거리를 구했기 때문에 두 경로의 최단 거리 중 더 짧은 거리를 출력합니다.
- 주어진 간선 정보를 HashMap 변수 map에 입력합니다.
- 다익스트라 알고리즘을 이용하여 1번 정점부터 다른 정점들로의 최소 거리를 구합니다.
- 1번 정점부터 각 정점들까지의 최소 거리를 나타내는 HashMap 변수 distances를 생성하고 각 정점들에 대해 거리를 정수 최댓값으로 초기화합니다. 1번 정점에 대해서는 거리를 0으로 초기화합니다.
- 각 정점들을 탐색하기 위해 PriorityQueue 변수 queue를 생성하고 1번 정점 및 1번 점점의 distances 값을 queue에 넣어줍니다.
- queue가 비워지기 전까지 반복문을 돌면서 1번 정점부터 각 정점들로의 최소 거리를 구합니다.
- queue에서 우선순위가 가장 높은 정점 및 해당 정점의 distances 값을 뽑아냅니다.
- 현재 위치한 도시의 정점까지의 최소 비용이 현재 위치한 정점의 distances 값보다 크다면 다음 queue의 도시로 넘어갑니다.
- 그렇지 않다면 현재 위치한 정점과 연결된 정점들을 nodeList라는 ArrayList에 담습니다.
- nodeList에 있는 모든 도시들을 돌면서 최소 거리를 구합니다.
- 현재 위치한 정점의 현재까지의 최소 거리와 현재 nodeList에 있는 정점까지의 거리를 더하여 거리를 계산한 후 해당 거리가 현재 nodeList에 있는 정점의 distances 값보다 작다면 해당 거리로 distances 값을 변경하고 queue에 현재 nodeList에 있는 정점 및 해당 거리를 넣어줍니다.
- 2번의 다익스트라 알고리즘 과정과 마찬가지로 u번 정점부터 다른 정점들로의 최소 거리를 구합니다.
- 2번의 다익스트라 알고리즘 과정과 마찬가지로 v번 정점부터 다른 정점들로의 최소 거리를 구합니다.
- (1 -> u -> v -> N) 경로의 최단 거리를 나타내는 변수 st1을 생성하고 정수의 최댓값으로 초기화합니다.
- (1 -> v -> u -> N) 경로의 최단 거리를 나타내는 변수 st2를 생성하고 정수의 최댓값으로 초기화합니다.
- (1 -> u -> v -> N) 경로의 최단 거리를 구하여 st1에 넣어줍니다.
- 만약 1번 정점부터 u번 정점까지의 거리가 정수의 최댓값이 아니고 u번 정점부터 v번 정점까지의 거리가 정수의 최댓값이 아니며 v번 정점부터 N번 정점까지의 거리가 정수의 최댓값이 아니라면 (1번 정점에서 u번 정점으로 가는 최단 거리 + u번 정점에서 v번 정점으로 가는 최단 거리 + v번 정점에서 N번 정점으로 가는 최단 거리)를 구해줍니다.
- (1 -> v -> u -> N) 경로의 최단 거리를 구하여 st2에 넣어줍니다.
- 만약 1번 정점부터 v번 정점까지의 거리가 정수의 최댓값이 아니고 v번 정점부터 u번 정점까지의 거리가 정수의 최댓값이 아니며 u번 정점부터 N번 정점까지의 거리가 정수의 최댓값이 아니라면 (1번 정점에서 v번 정점으로 가는 최단 거리 + v번 정점에서 u번 정점으로 가는 최단 거리 + u번 정점에서 N번 정점으로 가는 최단 거리)를 구해줍니다.
- 만약 st1과 st2가 모두 정수의 최댓값이라면 1번 정점부터 u, v 정점을 거쳐 N번 정점까지 도달할 수 없다는 뜻이므로 -1을 출력합니다.
- 그렇지 않다면 st1과 st2 중 더 작은 값을 출력합니다.
자바, 웹 개발을 열심히 공부하고 있습니다!