문제
https://www.acmicpc.net/problem/9370
풀이
- 그래프는
n개의 교차로와m개의 도로로 이루어져 있다. - 출발지
s와 두 교차로g,h가 주어진다. - 도로는 양방향이며 길이가 있다.
- 후보 목적지의 개수
t가 주어지고, 이후t개의 교차로 번호가 후보 목적지로 주어진다. - 출발지
s에서 각 후보 목적지까지 가는 최단 경로 중 특정 도로(g와 h를 잇는 도로)를 반드시 지나는가를 확인 - 해당 조건을 만족하는 후보 목적지만 오름차순으로 출력한다.
출발지에서 목적지까지의 최단 경로 중 특정한 간선을 지나는지 확인하는 Dijkstra(다익스트라) 문제입니다.
처음 문제를 접했을 때, 문제 해석을 하는 데에 오래 걸렸읍니다..
입력도 너무 많아 헷갈리기 쉬운 문제였던 거 같네요..
그래도 천천히 읽으면서 손으로 써보시면 금방 이해할 수 있습니다.
이 문제는 출발지(s)에서 t개의 도착지로 가는 최단 경로 중 g -> h 간선을 포함하는 최단 경로가 있는지 판단하면 되는 문제입니다.
저는 이를 파악하기 위해 다음과 같은 경로를 구하였습니다.
s -> g -> h -> x(x는 도착지)s -> h -> g -> x
이 경로가 s -> x의 최단 경로와 일치한다면, 답이 되지 않을까? 하여 이러한 경로를 구했습니다.
입력
// 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, d));
graph.get(b).add(new Node(a, d));
if ((a == g && b == h) || (a == h && b == g)) W = d;
}
// 목적지 후보
target = new int[t];
for (int i = 0; i < t; i++) {
target[i] = Integer.parseInt(br.readLine());
}n, m, t, s, g, h는 너무 길어 생략했습니다.graph는 인접리스트를 활용하였습니다.- 각 인덱스는 출발 지점을 나타내고 도착지점 번호와 그에 대한 가중치를
Node로 감싸 저장하였습니다. - 양방향 그래프이므로 역방향도 노드도 추가하였습니다.
- 정답을 구할 때,
g -> h간선은 항상 사용해야 하니 따로 저장하였습니다.
static class Node implements Comparable<Node> {
int idx, cost;
public Node (int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}Node클래스- 도착지 인덱스와 그에 대한 가중치를 저장하기 위해 선언하였습니다.
- 최단 경로를 구하기 위해
cost를 기준으로 정렬해주었습니다.
최단경로 탐색(Dijkstra)
private static int[] dijkstra(int start) {
int[] dist = new int[n+1]; // 각 노드까지의 거리를 저장할 배열
Arrays.fill(dist, INF); // 최단 거리를 찾아야 하므로 최댓값으로 초기화
dist[start] = 0; // 시작 지점은 0
// 최소 힙
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0)); // 노드, 이동거리
while (!pq.isEmpty()) {
Node cur = pq.poll(); // 현재 좌표, 이동한 거리
int u = cur.idx;
int d = cur.cost;
if (dist[u] < d) continue; // 만약 현재 저장된 최단 거리보다 길 경우 pass
// 인접 노드 검사
for (Node nxt : graph.get(u)) {
int v = nxt.idx;
int w = nxt.cost;
// 현재 저장된 최단 거리보다 경유하는 것이 더 짧을 경우 업데이트
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
return dist; // 최단경로를 모두 구했으면 배열 리턴
}- 다익스트라 메서드
- 일반적인 다익스트라 메서드입니다.
- 최소힙을 이용해 구현하였습니다.
경로 비교
private static void solve() {
Arrays.sort(target);
int[] distS = dijkstra(s); // 시작점이 s인 경우 최단 경로
int[] distG = dijkstra(g); // 시작점이 g일 경우 최단 경로
int[] distH = dijkstra(h); // 시작점이 h일 경우 최단 경로
// 목적지를 갖고 탐색
for (int i : target) {
// 만약 s -> i 와 s -> g -> h -> i 가 같을 경우 정답 추가
if (distS[i] == distS[g] + W + distH[i]) {
sb.append(i).append(' ');
}
// 만약 s -> i 와 s -> h -> g -> i 가 같을 경우 정답에 추가
else if (distS[i] == distS[h] + W + distG[i]){
sb.append(i).append(' ');
}
}
sb.append('\n');
}s -> g -> h -> x와s -> h -> g -> x의 경로가 최단 경로를 이루는지 찾는 메서드g -> h를 지나는 경로가 최단 경로일 경우 정답에 추가
코드
import java.util.*;
import java.io.*;
public class Main_9370 {
static class Node implements Comparable<Node> {
int idx, cost;
public Node (int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
static StringBuilder sb = new StringBuilder();
static int n, m, t; // 교차로, 도로, 목적지 후보
static int s, g, h; // 출발지, 지나야 하는 간선의 정보
static List<ArrayList<Node>> graph; // 노드, 간선의 정보를 담은 그래프
static int W; // g-h 가중치
static int[] target; // 목적지 후보
static final int INF = 1_000_000_000;
private static void solve() {
Arrays.sort(target);
int[] distS = dijkstra(s);
int[] distG = dijkstra(g);
int[] distH = dijkstra(h);
for (int i : target) {
if (distS[i] == distS[g] + W + distH[i]) {
sb.append(i).append(' ');
} else if (distS[i] == distS[h] + W + distG[i]){
sb.append(i).append(' ');
}
}
sb.append('\n');
}
private static int[] dijkstra(int start) {
int[] dist = new int[n+1];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0)); // 노드, 이동거리
while (!pq.isEmpty()) {
Node cur = pq.poll();
int u = cur.idx;
int d = cur.cost;
if (dist[u] < d) continue;
for (Node nxt : graph.get(u)) {
int v = nxt.idx;
int w = nxt.cost;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
return dist;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
t = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
s = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, d));
graph.get(b).add(new Node(a, d));
if ((a == g && b == h) || (a == h && b == g)) W = d;
}
target = new int[t];
for (int i = 0; i < t; i++) {
target[i] = Integer.parseInt(br.readLine());
}
solve();
}
System.out.println(sb.toString());
}
}