[3860번][C/C++] 할로윈 묘지

https://www.acmicpc.net/problem/3860

3860번: 할로윈 묘지

W x H 크기의 맵이 있는데 맵의 (0, 0)에서 (W-1, H-1)까지 탈출할 수 있는지 없는지, 혹은 무한 루프가 존재할 수 있는지 알아내는 문제이다.

 

맵에는 잔디, 묘비, 귀신 구멍이 있다.

세 요소를 정리해서 문제를 단순화해서 이해해보자.

- 잔디 : 빈 칸 (지나갈 수 있는 칸), 이 칸으로 올 때, 간선의 가중치는 1이다.

- 묘비 : 벽 (지나갈 수 없는 칸)

- 귀신 구멍 : 상하좌우론 갈 수 없고 단방향 간선만 하나 가진 칸 (음의 가중치를 가질 수 있는 간선), 이 간선은 음의 가중치를 가질 수 있다.

 

이렇게 문제 요소를 단순화 해서 이해한다면 그저 음의 간선을 가진 그래프에서 목적지에 도달할 수 있는가? 혹은 음의 사이클이 생기는가?를 물어보는 문제로 이해할 수 있다.

음의 사이클을 탐지하기 위해서 벨만 포드 알고리즘을 이용하면 된다.

 

벨만 포드 알고리즘은 다음과 같다.

먼저 N개의 노드가 있을 때, 모든 노드에 대해서 모든 간선을 러프하게 그때그때의 최단거리로 갱신하는 작업을 N-1번 한다. (N-1번이 핵심이다.)

이 때 음의 사이클이 존재하지 않는다면 이미 모든 노드에 대한 최단 거리가 구해진 상태이다.

하지만 음의 사이클이 존재한다면 계속 최단 거리가 갱신될 것이므로 N-1번에서 한 번 더 최단 거리를 구한다면 최단 거리가 갱신될 것이다.

이 원리를 이용해서 음의 사이클의 존재여부를 찾아내거나 음의 사이클이 없다면 그냥 최단 거리를 구할 수 있는 알고리즘이다.

 

이 문제는 벨만 포드 알고리즘을 2차원 맵에서 구현할 수 있는지 물어보는 문제이다.

특별한 스킬은 없고 문제를 보고 벨만 포드를 생각해 낸 뒤, 문제 조건에 맞게 정확하게 구현하는 문제이다.

나는 구현할 때, 귀신 구멍에서 최단 거리를 갱신할 때는 그 칸에서 상하좌우는 갈 수 없게 continue를 사용해서 막아줬다.

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <stack>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <deque>
#define INF 987654321

using namespace std;

pair<int, pair<int, pair<int, int>>> map[31][31]; // { 0:잔디  1:묘비  2:귀신 구멍, {간선의 무게, {도착y, 도착x}}}
int dist[31][31]; // (0,0)에서 모든 좌표에 대한 최단거리
int direc[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int W, H, G, E, totalVertex;
int X, Y;


bool isIn(int y, int x) {
	if (0 <= y && y <= H && 0 <= x && x <= W ) return true;
	else return false;
}

bool canGo(int y, int x) {
	if (isIn(y, x) && map[y][x].first != 1) return true;
	else return false;
}

bool bellman_ford(int sy, int sx) {
	dist[sy][sx] = 0;

	for (int t = 0; t <= totalVertex; t++) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				int cY = i, cX = j;
				if (cY == H - 1 && cX == W - 1) continue;

				if (map[cY][cX].first == 2) { // 귀신 구멍인 경우
					int nY = map[cY][cX].second.second.first;
					int nX = map[cY][cX].second.second.second;
					int nT = map[cY][cX].second.first;

					if (dist[cY][cX] != INF && dist[nY][nX] > dist[cY][cX] + nT) {
                        if (t == totalVertex) return true;
						dist[nY][nX] = dist[cY][cX] + nT;
					}
					continue;
				}
				
				for (int k = 0; k < 4; k++) {
					int nY = cY + direc[k][0];
					int nX = cX + direc[k][1];

					if (canGo(nY, nX)) {
						if (dist[cY][cX] != INF && dist[nY][nX] > dist[cY][cX] + 1) {
                            if (t == totalVertex) return true;
							dist[nY][nX] = dist[cY][cX] + 1;
						}
					}
				}
			}
		}
	}

	return false;
}

void init() {
	for (int i = 0; i < 31; i++) {
		for (int j = 0; j < 31; j++) {
			dist[i][j] = INF;
			map[i][j] = { 0, {1, {1, 1}} };
		}
	}
}

int main()
{
	while (1) {
		// initialize
		scanf("%d %d", &W, &H);
		if (W == 0 && H == 0) break;
		totalVertex = W * H - 1;
		init();

		int x, y;
		scanf("%d", &G);
		for (int i = 0; i < G; i++) {
			scanf("%d %d", &x, &y);
			map[y][x].first = 1;
		}

		int x1, y1, x2, y2, t;
		scanf("%d", &E);
		for (int i = 0; i < E; i++) {
			scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &t);
			map[y1][x1].first = 2;
			map[y1][x1].second.first = t;
			map[y1][x1].second.second.first = y2;
			map[y1][x1].second.second.second = x2;
		}

		if (bellman_ford(0, 0)) {
			printf("Never\n");
			continue;
		}

		if (dist[H - 1][W - 1] == INF) printf("Impossible\n");
		else printf("%d\n", dist[H - 1][W - 1]);
	}

	return 0;
}