BOJ_3860 할로윈 묘지 (C++)

↑클릭 시 문제로 이동

개요

벨만 포드의 기초에 살짝 귀찮은 구현을 추가한 문제로 조금 신경써야 할 부분이 있다.
먼저 2차원 배열의 형태로 묘지가 주어지는데 이를 그래프로 생각해 각 간선들을 뽑아줘야 하며, 이때 묘비가 있는 위치, 귀신 구멍이 있는 위치 등을 고려해야 한다.
편의를 위해 enum 자료형을 다음과 같이 정의했다.

enum {
    BLANK, RIP, GIN, END // GIN = position into Ghost hole
};

---

그래프 간선

먼저 입력을 받으며 묘지에 묘비 위치를 체크해준다.
또한 귀신 구멍의 시작 위치와 끝 위치를 이어주는 간선을 만든다. 이때 묘지에서 귀신 구멍의 시작 위치를 체크해준다. (map[X1][Y1] = GIN;) 이후 이웃한 칸으로 이동하는 모든 간선을 찾을 때 귀신 구멍의 시작점에서는 반드시 귀신 구멍의 끝점으로만 나와야 하기 때문이다.

그리고 map[W - 1][H - 1] = END도 하는데, 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이기 때문이다. 즉, 출구에서는 다른 칸으로 이동하지 않는다.

이제 모든 BLANK로 지정된 map의 칸들에 대해 네 방향으로의 모든 길이가 1인 간선들을 찾는다. 범위체크는 물론이고, 묘비로도 이동하지 않도록 예외처리를 한다.

---

벨만 포드

모든 간선을 찾았다면 벨만 포드 알고리즘을 수행한다. 이때 노드의 개수인 N은 W * H - G이다.
for문을 N번째로 시행할 때 최단경로의 변화가 있다면 계속해서 과거로 돌아간다는 의미이므로 Never를 출력한다.

---

틀렸던 부분

첫번째로는 위에서 말했듯 상근이는 출구에 도착하면 바로 빠져나가므로 목적지에서는 간선을 만들면 안되었다.

또 처음엔 귀신 구멍의 끝점도 GOUT으로 잡고 다음과 같이 묘지에 체크했었다. (물론 간선 찾는 부분에서는 BLANK와 똑같이 찾아줌)

for (int i = 0; i < E; i++) {
    cin >> X1 >> Y1 >> X2 >> Y2 >> T;
    e.push_back(make_tuple(make_pair(X1, Y1), make_pair(X2, Y2), T));
    map[X2][Y2] = GOUT;
    map[X1][Y1] = GIN;
}

그러나 귀신 구멍이 여러개일 경우, 앞서 GIN으로 체크된 부분이 이후에 GOUT으로 덮어씌워질 수 있다. 이 경우에 틀리게 된다.
불필요한 처리는 하지 말자…! (╯°□°）╯︵ ┻━┻

---

코드

/* BOJ_3860 할로윈 묘지 */
/* hanabzu */

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <tuple>
#include <string.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<pii, pii, int> TUP;

enum {
	BLANK, RIP, GIN, END // GIN = position into Ghost hole
};

const int MAXN = 30;
const int INF = 1987654321;
const int dx[4] = { 0,0,-1,1 };
const int dy[4] = { -1,1,0,0 };

int map[MAXN][MAXN];
int d[MAXN][MAXN];
int W, H, G, X, Y, E, X1, Y1, X2, Y2, T, N;

void testcase();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (1) {
		cin >> W >> H;
		if (W == 0) break;
		testcase();
	}

	return 0;
}


void testcase() {
	memset(map, BLANK, sizeof(map));
	fill(&d[0][0], &d[MAXN - 1][MAXN], INF);

	vector<TUP> e;

	cin >> G;

	for (int i = 0; i < G; i++) {
		cin >> X >> Y;
		map[X][Y] = RIP;
	}

	cin >> E;
	for (int i = 0; i < E; i++) {
		cin >> X1 >> Y1 >> X2 >> Y2 >> T;
		e.push_back(make_tuple(make_pair(X1, Y1), make_pair(X2, Y2), T));
		map[X1][Y1] = GIN;
	}

	map[W - 1][H - 1] = END;
	for (int i = 0; i < W; i++) {
		for (int j = 0; j < H; j++) {
			if (map[i][j] == BLANK) {
				for (int d = 0; d < 4; d++) {
					int ni = i + dx[d];
					int nj = j + dy[d];
					if (ni < 0 || ni >= W || nj < 0 || nj >= H || map[ni][nj] == RIP) continue;
					e.push_back(make_tuple(make_pair(i, j), make_pair(ni, nj), 1));
				}
			}
		}
	}

	N = W * H - G; // num of nodes

	// bellman ford
	d[0][0] = 0;
	pii a, b;
	int c;
	for (int i = 0; i < N; i++) {
		for (vector<TUP>::iterator it = e.begin(); it != e.end(); it++) {
			a = get<0>(*it); b = get<1>(*it); c = get<2>(*it);
			if (d[a.first][a.second] != INF && d[b.first][b.second] > d[a.first][a.second] + c) {
				d[b.first][b.second] = d[a.first][a.second] + c;
				if (i == N - 1) {
					cout << "Never\n";
					return;
				}
			}
		}
	}

	if (d[W - 1][H - 1] == INF) {
		cout << "Impossible\n";
	}
	else {
		cout << d[W - 1][H - 1] << '\n';
	}
}

---

오타 수정, 알고리즘 질문 등은 댓글로 남겨주세요. 감사합니다. 😁