1. 문제
https://www.acmicpc.net/problem/3860
2. 접근법
벨만-포드(Bellman-Ford) 알고리즘
단일 시작점 (y1, x1)에서 단일 도착점 (y2, x2)까지의 최단 경로를 묻는 문제이다. 귀신 구멍의 경우 음수의 가중치를 가질 수 있으니, 벨만-포드 알고리즘을 사용해야 한다.
묘지는 배열 형태로 주어지지만, 이는 쉽게 위와 같이 그래프 형태로 변경할 수 있다. 묘지를 제외한 인접하는 칸을 서로 연결하면 된다.
이 후, 벨만 포드 알고리즘을 사용해 최소 거리를 구한다. 만약 음의 사이클(Negative Cycle)이 발생하면 Never를, 도착점이 INF 값이면 Impossible을 출력하면 된다.
시간 복잡도
벨만-포드 알고리즘의 시간복잡도는 O(VE) (V=정점의 수, E=간선의 수) 이고, 묘지의 크기가 1 <= 길이, 높이 <= 30 이므로 최대 연산 수가 (30 x 30) x ((29 x 29) + (29 x 29)) = 1,513,800 이 되어 시간초과가 되지 않는다.
3. 유의할 점
귀신 구멍에서는 인접한 칸으로 이동할 수 없다.
귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이전)에 평행 우주의 다른 구멍에서 나오게 된다.
귀신 구멍이 있는 칸에 도달하면, 무조건 구멍에 떨어지게 되며 인접한 칸으로는 이동할 수 없다. 간선을 연결할 때, 인접한 칸에서 귀신 구멍으로 가는 간선은 연결하되, 귀신 구멍에서 나오는 간선은 연결하지 말아야 한다.
도착점에서는 이동할 수 없다.
상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다.
상근이는 도착점에 도달하는 순간, 다른 인접한 칸으로 이동할 수 없다. 문제에서 그렇게 명시했을 뿐더러, 만약 도착점에서 이동하면 아례와 같은 반례가 생길 수 있다.
정답은 (4, 1) ... (4, 4) .... (1, 4)로 이어지는 경로이지만, 도착 지점에서 더 이동하게 된다면 (1, 1)의 귀신 구멍을 이용한 경로가 최단 경로가 된다.
4. 코드
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class p3860 {
static class Point {
int y, x;
Point(int y, int x) {
this.y = y;
this.x = x;
}
}
static class Edge {
Point p1, p2;
int weight;
Edge(Point p1, Point p2, int weight) {
this.p1 = p1;
this.p2 = p2;
this.weight = weight;
}
}
static int W, H, G, E;
static final int INF = Integer.MAX_VALUE;
static ArrayList<Edge> map;
static int[][] status, dist;
static void bellmanFord() {
dist[0][0] = 0;
// 귀신 구멍은 정점이 아니므로 뺴주기
for (int i = 0; i < ((W * H) - G) - 1; i ++) {
for (Edge edge : map) {
if (dist[edge.p1.y][edge.p1.x] != INF) {
int nextDist = dist[edge.p1.y][edge.p1.x] + edge.weight;
if (nextDist < dist[edge.p2.y][edge.p2.x]) {
dist[edge.p2.y][edge.p2.x] = nextDist;
}
}
}
}
}
static boolean checkNegativeCycle() {
for (Edge edge : map) {
if (dist[edge.p1.y][edge.p1.x] != INF) {
int nextDist = dist[edge.p1.y][edge.p1.x] + edge.weight;
if (nextDist < dist[edge.p2.y][edge.p2.x]) {
return true;
}
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
if (W == 0 && H == 0) break;
map = new ArrayList<>();
status = new int[H][W];
dist = new int[H][W];
G = Integer.parseInt(br.readLine());
for (int i = 0; i < G; i ++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// -1 = 귀신 구멍, 0 = 이동 가능한 칸, 1 = 묘지
status[y][x] = 1;
}
E = Integer.parseInt(br.readLine());
for (int i = 0; i < E; i ++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(st.nextToken());
map.add(new Edge(new Point(y1, x1), new Point(y2, x2), T));
status[y1][x1] = -1;
}
for (int y = 0; y < H; y ++) {
for (int x = 0; x < W; x ++) {
dist[y][x] = INF;
// 도착점, 귀신 구멍이면 continue
if (y == (H - 1) && x == (W - 1)) continue;
if (status[y][x] == -1) continue;
// 현재 위치에서 묘지를 제외한 인접점 연결
Point curtPoint = new Point(y, x);
if (y > 0 && status[y - 1][x] != 1)
map.add(new Edge(curtPoint, new Point(y - 1, x), 1));
if (y < (H - 1) && status[y + 1][x] != 1)
map.add(new Edge(curtPoint, new Point(y + 1, x), 1));
if (x > 0 && status[y][x - 1] != 1)
map.add(new Edge(curtPoint, new Point(y, x - 1), 1));
if (x < (W - 1) && status[y][x + 1] != 1)
map.add(new Edge(curtPoint, new Point(y, x + 1), 1));
}
}
bellmanFord();
if (checkNegativeCycle()) {
System.out.println("Never");
} else if (dist[H - 1][W - 1] == INF) {
System.out.println("Impossible");
} else {
System.out.println(dist[H - 1][W - 1]);
}
}
}
}
