BOJ : 3860 할로윈 묘지

---

[BOJ 3860(P5)리뷰]

시작점부터 시작하여 목적지까지 도착해야 한다. 묘지가 있는곳으로는 이동할 수 없으며, 귀신 구멍이라는 특정한 칸으로 이동하면 다른 곳으로 시간을 워프하여 이동할 수 있다. 이때 시간을 과거로 되돌릴 수 있다.

인접한 칸을 간선으로 갖고, 귀신 구멍이라는 특별한 간선을 갖는 그래프라고 생각하면 된다. 다만, 과거로 되돌아 갈 수 있다고 했으니 음의 가중치를 갖는 그래프이다.

문제에서 최단거리를 구하라 했으니 최단거리를 구하는 알고리즘을 사용해야 한다. 시작지와 목적지가 주어져 있으므로 다익스트라 알고리즘이 적합하겠지만, 간선에 음의 가중치가 붙을 수 있으므로 벨만포드 알고리즘을 사용해야 한다.

만약 음의 사이클이 존재하면 "Never"를, 음의 사이클은 존재하지 않지만 목적지에 도착할 수 없으면 "Impossible"을, 목적지에 도착했다면 최단거리를 출력하면 된다.

시작점부터 시작하여 벨만포드 알고리즘을 수행하면 된다. 다만 이 때 생각해야 할점은 "이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다"라는 조건을 생각하여 목적지에서는 간선 update가 이루어지지 않도록 해야 한다.

나는 "들어가는 구멍과 나오는 구멍이 같을 수 있다"라는 조건을 못봐서 이것때문에 매우 삽질을 했다..

문제 조건을 잘 읽자.

/*
	21.01.20
	BOJ : 3860 할로윈 묘지 (https://www.acmicpc.net/problem/3860)
	벨만포드 알고리즘
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
struct info {
	int r;
	int c;
	int t;
};
int w, h ,g, e;
int board[31][31];
info hole[31][31];
ll dist[32][32];
bool isCycle;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

void init() {
	memset(board, 0, sizeof(board));
	memset(hole, 0, sizeof(hole));
}

bool bellman() {
	//거리 초기화
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			dist[i][j] = INT_MAX;
		}
	}

	dist[0][0] = 0; //시작점의 거리는 0

	for (int i = 0; i < w * h - g; i++) { //전체 크기에서 묘지의 갯수를 뺀게 정점의 갯수.
		for (int j = 0; j < w; j++) { //행
			for (int k = 0; k < h; k++) { //열
				//아직 방문한적이 없는 정점이나, 묘지이거나, 목적지인경우 거리 update하지 않음.
				if (dist[j][k] == INT_MAX || board[j][k] == 1 || (j == w - 1 && k == h - 1)) continue;

				if (board[j][k] != 2) { //구멍이 아닐경우 (잔디)
					for (int dir = 0; dir < 4; dir++) { //인접한 네 방향에 대해서 탐색
						int nx = j + dx[dir];
						int ny = k + dy[dir];
						if (nx < 0 || ny < 0 || nx >= w || ny >= h || board[nx][ny] == 1) continue; //범위응 벗어나거나 묘지일경우 스킵
						if (dist[nx][ny] > dist[j][k] + 1) {
							dist[nx][ny] = dist[j][k] + 1;
							if (i == w * h - g - 1) { //이때 업데이트가 이루어지면 음의사이클 존재
								return true;
							}
						}
					}
				}
				else {
					//현재 구멍의 다음 이동위치 정보받아서
					int nx = hole[j][k].r;
					int ny = hole[j][k].c;
					int nt = hole[j][k].t;

					if (dist[nx][ny] > dist[j][k] + nt) { 
						dist[nx][ny] = dist[j][k] + nt; //거리 업데이트
						if (i == w * h - g - 1) {
							return true;
						}
					}
				}
			}
		}
	}

	return false;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (true) {
		cin >> h >> w;
		if (h + w == 0) break;
		init();

		cin >> g;
		for (int i = 0; i < g; i++) {
			int r, c;
			cin >> c >> r;
			board[r][c] = 1; //잔디일경우 board에 1로 표기
		}

		cin >> e;

		for (int i = 0; i < e; i++) {
			int x1, x2, y1, y2, t;
			cin >> y1 >> x1 >> y2 >> x2 >> t;
			board[x1][y1] = 2; //들어가는 구멍일경우 2로 표기
			hole[x1][y1] = { x2,y2,t }; //정보 넣기
		}

		isCycle = bellman();

		if (isCycle) {
			cout << "Never\n";
		}
		else {
			if (dist[w - 1][h - 1] == INT_MAX) {
				cout << "Impossible\n";
			}
			else {
				cout << dist[w - 1][h - 1] << '\n';
			}
		}
	}

	return 0;
}