[백준] 9370. 미확인 도착지
문제 링크
풀이 과정
풀이 1
다익스트라 알고리즘을 적용해 풀 수 있는 문제입니다. 시작 정점으로부터 목적지 후보 정점에 도착했을 때, 최단 거리 경로에 g-h 간선이 포함되는 지 판단해야 합니다.
문제를 풀며 주의해야 할 조건은 다음과 같습니다.
- g-h 간선의 사용 유무를 저장해 두어야 합니다.
- 정점까지 같은 비용으로 가더라도, g-h 간선을 포함해 가는 경로가 있다면, 해당 정점까지는 g-h 간선을 이용해 간 것으로 설정해 줘야 합니다.
private static class Edge {
int vertex, cost;
}
private static class Info {
int dist;
boolean used;
}
위 코드와 같이 간선 정보를 저장하는 클래스 Edge와 별개로, 간선에 대한 최단 거리( dist ) 및 g-h 간선의 사용 유무( used )를 체크하기 위한 Info 클래스를 하나 두었습니다.
또한, 정점까지 도달하는 데에 드는 비용이 같다면, 이전 경로는 무시하고 g-h 간선을 사용하도록 해주어야 합니다.
위 예시처럼, 같은 비용의 다른 경로가 존재하고, 그 경로(파란색 경로)가 g-h 간선을 포함한다면, g-h 간선을 이용해 간 것으로 판단해줘야 합니다. 다시 말해, g-h 간선을 이용해서 도달이 가능하다고 판단해 주어야 합니다.
for (Edge next : adj[now.vertex]) {
if (!visit[next.vertex] && infos[next.vertex].dist >= infos[now.vertex].dist + next.cost) {
if(infos[next.vertex].used && infos[next.vertex].dist == infos[now.vertex].dist + next.cost) continue;
infos[next.vertex].dist = infos[now.vertex].dist + next.cost;
infos[next.vertex].used = infos[now.vertex].used;
Edge edge = new Edge(next.vertex, infos[next.vertex].dist);
pq.add(edge);
if ((now.vertex == g && next.vertex == h) || (now.vertex == h && next.vertex == g)) {
infos[next.vertex].used = true;
}
}
}
아직 방문하지 않은 인접한 정점에 대해 아래와 같은 과정을 거칩니다.
- 다음 정점에 대해, 이미 저장되어 있는 최소 비용과 현재 정점까지의 최소 비용에 다음 정점까지의 비용을 더했을 때의 비용이 같고, g-h 간선을 사용한 이력이 있으면 갱신 및 큐에 삽입하는 과정은 생략합니다.
- 이미 저장되어 있는 최소 비용보다 현재 정점까지의 최소 비용에 다음 정점까지의 비용을 더했을 때의 비용이 작다면, 갱신시켜 줍니다. 이 때, 현재 정점과 다음 정점이 g, h 쌍이라면 g-h 간선의 사용 유무를 체크(used 를 true 로) 해줍니다.
풀이 2
출발지로부터 목적지 후보까지 간선 g-h 를 포함하는 경로는 다음과 같이 두 가지로 구분됩니다.
출발지 → g → h → 목적지 후보
출발지 → h → g → 목적지 후보
또한, 최단 거리로 이동하므로, 각 부분 경로들도 최단 비용을 만족해야 합니다. 다시 말하면, 출발지로부터 목적지 후보까지의 최단 거리는 아래 두 경우 중 하나 이상 만족해야만 간선 g-h를 이용했다고 판단할 수 있습니다. 아니고서는 g-h 간선을 이용하지 않은 경로로 간주할 수 있습니다.
출발지 → 목적지 후보 최단 거리
= (출발지 → g 최단 거리) + (g-h 간선 비용) +( h → 목적지 후보 최단 거리)
OR (출발지 → h 최단 거리) + (h-g 간선 비용) + (g → 목적지 후보 최단 거리)
해당 풀이는 각 정점 s, g, h 에 대해서 다익스트라를 각각 수행(총 세 번)합니다. 이렇게 얻어진 출발지를 다르게 돌렸을 때 각 정점에 대한 최단거리 역시 서로 다른 배열( dist_s , dist_g , dist_h ) 에 저장하고 갱신합니다.
if (dist_s[idx] == dist_s[g] + dist_g[h] + dist_h[idx]
|| dist_s[idx] == dist_s[h] + dist_h[g] + dist_g[idx]) {
candidate.put(idx, true);
}
위 코드는 간선 g-h를 사용했나 판단하는 과정입니다. 위에서 적은 것처럼, dist_s[idx] == dist_s[g] + dist_g[h] + dist_h[idx] 는 최단거리로 먼저 g를 방문한 후 이후 h, 목적지 순으로 비용을 더해 해당 비용이 최소 비용을 만족하는 지, dist_s[idx] == dist_s[h] + dist_h[g] + dist_g[idx] 는 최단거리로 먼저 h를 방문한 이후 g, 목적지 순으로 비용을 더해 해당 비용이 최소 비용을 만족하는 지를 판별합니다. 두 경우 중 하나만 만족하더라도 간선 g-h를 사용해 최단 비용으로 목적지 후보에 도달했다는 결론을 내릴 수 있습니다.
코드
풀이 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, t, s, g, h;
static ArrayList<Edge>[] adj;
static Info[] infos;
static boolean[] visit;
static TreeMap<Integer, Boolean> candidate;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= TC; 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());
adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++)
adj[i] = new ArrayList<>();
infos = new Info[n + 1];
for (int i = 1; i <= n; i++)
infos[i] = new Info(Integer.MAX_VALUE, false);
visit = new boolean[n + 1];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int v1, v2, cost;
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
adj[v1].add(new Edge(v2, cost));
adj[v2].add(new Edge(v1, cost));
}
candidate = new TreeMap<>();
for (int i = 0; i < t; i++)
candidate.put(Integer.parseInt(br.readLine()), false);
PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.cost - o2.cost;
}
});
infos[s].dist = 0;
Edge start = new Edge(s, 0);
pq.add(start);
while (!pq.isEmpty()) {
Edge now = pq.poll();
visit[now.vertex] = true;
if (candidate.containsKey(now.vertex) && infos[now.vertex].used) {
candidate.put(now.vertex, true);
}
for (Edge next : adj[now.vertex]) {
if (!visit[next.vertex] && infos[next.vertex].dist >= infos[now.vertex].dist + next.cost) {
if(infos[next.vertex].used && infos[next.vertex].dist == infos[now.vertex].dist + next.cost) continue;
infos[next.vertex].dist = infos[now.vertex].dist + next.cost;
infos[next.vertex].used = infos[now.vertex].used;
Edge edge = new Edge(next.vertex, infos[next.vertex].dist);
pq.add(edge);
if ((now.vertex == g && next.vertex == h) || (now.vertex == h && next.vertex == g)) {
infos[next.vertex].used = true;
}
}
}
}
for (Map.Entry entry : candidate.entrySet()) {
if ((boolean) entry.getValue()) {
System.out.print(entry.getKey() + " ");
}
}
System.out.println();
}
}
private static class Edge {
int vertex, cost;
public Edge(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
}
private static class Info {
int dist;
boolean used;
public Info(int dist, boolean used) {
this.dist = dist;
this.used = used;
}
}
}
풀이 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, t, s, g, h;
static ArrayList<Edge>[] adj;
static int[] dist_s, dist_g, dist_h;
static boolean[] visit;
static TreeMap<Integer, Boolean> candidate;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= TC; 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());
adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++)
adj[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int v1, v2, cost;
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
adj[v1].add(new Edge(v2, cost));
adj[v2].add(new Edge(v1, cost));
}
candidate = new TreeMap<>();
for (int i = 0; i < t; i++)
candidate.put(Integer.parseInt(br.readLine()), false);
dist_s = new int[n + 1];
dist_g = new int[n + 1];
dist_h = new int[n + 1];
Arrays.fill(dist_s, Integer.MAX_VALUE);
Arrays.fill(dist_g, Integer.MAX_VALUE);
Arrays.fill(dist_h, Integer.MAX_VALUE);
dijkstra(s, dist_s);
dijkstra(g, dist_g);
dijkstra(h, dist_h);
for (Map.Entry entry : candidate.entrySet()) {
int idx = (int) entry.getKey();
if (dist_s[idx] == dist_s[g] + dist_g[h] + dist_h[idx]
|| dist_s[idx] == dist_s[h] + dist_h[g] + dist_g[idx]) {
candidate.put(idx, true);
}
}
for (Map.Entry entry : candidate.entrySet()) {
if ((boolean) entry.getValue()) {
System.out.print(entry.getKey() + " ");
}
}
System.out.println();
}
}
private static void dijkstra(int start, int[] dist) {
PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.cost - o2.cost;
}
});
visit = new boolean[n + 1];
dist[start] = 0;
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge now = pq.poll();
visit[now.vertex] = true;
for (Edge next : adj[now.vertex]) {
if (!visit[next.vertex] && dist[next.vertex] > dist[now.vertex] + next.cost) {
dist[next.vertex] = dist[now.vertex] + next.cost;
pq.add(new Edge(next.vertex, dist[next.vertex]));
}
}
}
}
private static class Edge {
int vertex, cost;
public Edge(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
}
}
댓글남기기