https://www.acmicpc.net/problem/1504
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
코드
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node implements Comparable<Node> {
int end;
int weight;
Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
public class No1504 {
static int N, E;
static int[] dist;
static ArrayList<ArrayList<Node>> graph;
static final int INF = 200000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
dist = new int[N + 1];
//노드 초기화
for (int i = 0; i <= N; i++)
graph.add(new ArrayList<>());
//값 입력 받고, 그래프에 초기화
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
//양방향 그래프를 만드는 부분
graph.get(start).add(new Node(end, weight));
graph.get(end).add(new Node(start, weight));
}
//반드시 거쳐야 하는 서로다른 정점 번호 받기
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//꼭 방문해야하는 두정점을 방문하는 경우 두가지
int case1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N); //1->v1->v2->N
int case2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N); //1->v2->v1->N
//꼭 거쳐가야 하는 두정점을 방문하는 두가지 경우중 더 짧은 것 선택
int result = (case1 >= INF && case2 >= INF) ? -1 : Math.min(case1, case2);
System.out.println(result);
br.close();
}
public static int dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
//배열 일괄 초기화
Arrays.fill(dist, INF);
//출발점 큐에 추가
pq.offer(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node nowNode = pq.poll();
int now = nowNode.end; //큐에서 node 인스턴스 추출
//최단 거리 구하는 로직
for (Node node : graph.get(now)) {
if (dist[node.end] > dist[now] + node.weight) {
dist[node.end] = dist[now] + node.weight;
pq.add(new Node(node.end, dist[node.end]));
}
}
}
return dist[end];
}
}
풀이
해당 문제는 가중치 개념이 있는 최소경로값을 구하는 문제이므로 다익스트라를 이용하여 풀면 된다.
1753번 문제에 특정 정점을 반드시 지나야된다는 조건이 추가 된 문제이다.
https://seaotter.tistory.com/33
특정 정점이 두개 이므로 정점을 지나는 방법은 아래와 같이 두가지이다.
1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N
이 두가지 케이스를 비교하여 더 짧은 것을 선택 하여 출력 하면 된다.
최단경로 푸는 방법
문제유형 | 푸는 방법 |
가중치 개념이 없는 최단 경로 문제 | BFS |
가중치 개념이 있는 한 노드 기준 최단 경로 문제 | 다익스트라 |
가중치 개념이 있는 여러 노드 기준 최단 경로 문제 | 플로이드 와샬 |
'코딩테스트' 카테고리의 다른 글
[그래프] 백준 4883번 삼각 그래프 자바 (Java) (0) | 2023.02.05 |
---|---|
[그래프] 백준 11403번 경로 찾기 자바 (Java) (0) | 2023.02.05 |
[최단경로] 백준 1753번 최단경로 자바 (Java) (0) | 2023.02.01 |
[최단경로] 백준 1446번 지름길 자바 (Java) (0) | 2023.02.01 |
[최단경로] 백준 14940 쉬운 최단거리 자바 (Java) (0) | 2023.01.31 |
댓글