[C++][백준] 할로윈 묘지(3860) - 벨만포드 알고리즘

문제

오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다.

상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이전)에 평행 우주의 다른 구멍에서 나오게 된다. 

묘지는 W × H 크기의 그리드로 나타낼 수 있다. 묘지의 입구는 (0, 0)이고, 출구는 (W-1, H-1)이다. 상근이는 겁이 많기 때문에, 최대한 빨리 묘지를 나가려고 한다. 그리고 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다. 상근이는 현재 있는 칸과 동, 서, 남, 북으로 인접한 칸으로 이동할 수 있다. 각 칸은 잔디, 묘비, 또는 귀신 구멍이다.

• 묘비는 매우 높기 때문에, 묘비가 있는 칸으로는 이동할 수 없다.
• 귀신 구멍이 있는 칸으로 이동하면, 특정 시간이 지난 후에 묘지의 다른 곳에서 상근이가 나타나게 된다. 시간은 귀신 구멍마다 다르며, 양수, 음수, 0 중 하나이다.
• 잔디가 있는 칸으로는 자유롭게 이동할 수 있다.

상근이는 묘지를 빨리 나가기 위해 귀신 구멍도 이용할 것이다. 묘지를 나갈 수 없는 경우나, 계속해서 과거로 이동하는 경우가 존재할 수도 있다.

 

묘지가 위와 같이 생긴 경우(문제의 두 번째 예제)를 살펴보자. 묘비는 (2,1)와 (3,1)에 있고, 귀신 구멍은 0초만에 (3,0)로 들어가서 (2,2)에서 나오는 구멍 하나가 있다. 묘지를 빠져나오는데 걸리는 가장 빠른 시간은 4초이며, 다음과 같다.

(0,0) -> 동(1초) (1,0) -> 동(1초) (2,0) -> 동(1초) (3,0) -> 귀신구멍(0초) (2,2) -> 동(1초) (3,2)

귀신 구멍을 이용하지 않는다면 가장 빠른 시간은 5초이다.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 묘지의 너비 W와 높이 H가 주어진다. (1 ≤ W, H ≤ 30) 다음 줄에는 묘비의 개수 G (G ≥ 0)가 주어진다. 다음 G개 줄에는 묘비의 위치를 나타내는 두 정수 X와 Y가 주어진다. (0 ≤ X < W, 0 ≤ Y < H)

다음 줄에는 귀신 구멍의 수 E (E ≥ 0)가 주어진다. 다음 E개 줄에는 귀신 구멍의 정보를 나타내는 X1, Y1, X2, Y2, T 가 주어진다. (X1, Y1)은 귀신 구멍의 위치이고, (X2, Y2)는 그 귀신 구멍으로 들어갔을 때, 나오는 곳의 위치이다. (0 ≤ X1, X2 < W, 0 ≤ Y1, Y2 < H) (X1,Y1)과 (X2,Y2)가 같을 수도 있다. T는 귀신 구멍에서 나오는데 걸리는 시간이다. (-10,000 ≤ T ≤ 10,000) T가 양수인 경우에는 귀신 구멍을 들어간 이후에 나온다는 의미이다. 두 귀신 구멍이 같은 장소에 있거나, 구멍에서 나오는 지점이 묘비인 경우는 없다. 묘비와 귀신 구멍이 (0, 0)이나 (W-1, H-1)에 있는 경우는 없다.

입력의 마지막 줄에는 0 0이 주어진다.

 

출력

각 테스트 케이스 마다 상근이가 과거로 계속해서 돌아간다면 "Never"를 출력하고, 출구를 빠져나올 수 없으면 "Impossible"을 출력한다. 그 외의 경우에는 묘지를 빠져나오는데 가장 빠른 시간을 출력한다.

 

풀이

음의 가중치가 있는 최단 경로 탐색 문제로 생각할 수 있습니다.

벨만포드 알고리즘을 사용하였습니다.

 

벨만포드 알고리즘은 아래 포스팅에서 자세히 다루었습니다.

vanilla-sue.tistory.com/78

[C++][백준] 타임머신(11657) - 벨만포드 알고리즘

2차원 배열을 Graph로 변환하여 문제를 해결하였습니다.이차원 배열의 인덱스인 x, y는 (x * W + y + 1) 식을 통해 중복없는 Integer 인덱스로 바꿀 수 있습니다.

 

Graph에 귀신 구멍을 통해 순간이동 할 수 있는 경로를 추가하고make_graph() 함수를 통해 동, 서, 남, 북으로 인접한 칸으로 이동하는 경로를 추가하였습니다.

 

make_graph() 함수에서 유의할 점이 있습니다. 

아래 조건문을 걸어주어야 합니다.

* 귀신 구멍에서는 동, 서, 남, 북 인접한 칸으로 이동하지 않습니다. 바로 시간 루프 구멍에 빠져버립니다.

* 언덕에서는 동, 서, 남, 북 인접한 칸으로 이동할 수 없습니다.

* 언덕으로는 이동할 수 없습니다.

 

마지막으로 음의 가중치가 있는 상황에서 최단 경로 탐색을 위해 벨만포드 알고리즘을 사용합니다.nagative_search() 함수에서 벨만포드 알고리즘을 진행하며 묘지를 나갈 수 없는 경우나, 계속해서 과거로 이동하는 경우 false를 return 합니다.

 

전체 소스는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int H, W;
int G, E;
const int MAX = 950;
const int MAX_COST = 987654321;
bool hill[35][35]; 
bool ghost[35][35];

int costs[MAX];
int N;

struct myData {
	int x;
	int y;
};
vector<int> myGraph[MAX];
vector<int> myCost[MAX];

int dirX[4] = { -1, 0, 1, 0 };
int dirY[4] = { 0, 1, 0, -1 };

void init() {
	for (int i = 0; i < 35; i++) {
		for (int j = 0; j < 35; j++) {
			hill[i][j] = false;
			ghost[i][j] = false;
		}
	}

	for (int i = 0; i < MAX; i++) {
		myGraph[i].clear();
		myCost[i].clear();
		costs[i] = MAX_COST;
	}

	N = W * H;
}

bool negative_search() {
	costs[1] = 0;
	for (int i = 1; i <= N; i++) { // 총 N번의 루프를 돈다.
		for (int j = 1; j < N; j++) { // 모든 노드에 대해서
			for (int k = 0; k < myGraph[j].size(); k++) { // 최단 경로를 갱신한다.
				int next = myGraph[j][k];
				int nextCost = myCost[j][k];

				if (costs[j] != MAX_COST && costs[j] + nextCost < costs[next]) {
					if (i == N) return true;
					costs[next] = costs[j] + nextCost;
				}
			}
		}
	}
	return false;
}

bool isInRange(int X, int Y) {
	if (X >= 0 && X < H && Y >= 0 && Y < W) return true;
	else return false;
}

int getNode(int x, int y) {
	return x * W + y + 1;
}

void make_graph() {
	for (int i = 0; i < H; i++) {    
		for (int j = 0; j < W; j++) { 
			if (hill[i][j] == true || ghost[i][j] == true || (i == H - 1 && j == W - 1)) continue; //귀신구멍확인

			for (int k = 0; k < 4; k++) {
				int nextX = i + dirX[k];
				int nextY = j + dirY[k];

				if (isInRange(nextX, nextY) && hill[nextX][nextY] == false) {
					int S = getNode(i, j);
					int E = getNode(nextX, nextY);

					myGraph[S].push_back(E);
					myCost[S].push_back(1);
				}
			}
		}
	}
}

int main() {
	while (true) {
		cin >> W >> H;

		if (H == 0 && W == 0) break;
		init();

		cin >> G;
		for (int i = 0; i < G; i++) {
			int X, Y;
			cin >> Y >> X; //Y넓이 X높이
			hill[X][Y] = true; //무덤
		}

		//myGraph, myCost 설정완료
		cin >> E;
		for (int i = 0; i < E; i++) {
			int X1, Y1, X2, Y2, T;
			cin >> Y1 >> X1 >> Y2 >> X2 >> T;

			int S = getNode(X1, Y1);
			int E = getNode(X2, Y2);

			myGraph[S].push_back(E);
			myCost[S].push_back(T);
			ghost[X1][Y1] = true; //귀신구멍
		}

		make_graph();

		if (negative_search()) {
			printf("Never\n");
		}
		else if (costs[N] == MAX_COST) {
			printf("Impossible\n");
		}
		else {
			printf("%d\n", costs[N]);
		}
	}

	return 0;
}