취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3860번 문제인 할로윈 묘지이다.
문제는 아래 링크를 확인하자.

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

귀신구멍을 이용하면 시간이 과거로 돌아가므로 음의 간선을 처리할 수 있는 최단거리 알고리즘을 이용하자.

글쓴이는 Bellman-Ford 알고리즘을 이용하였다.

주어진 묘지에서는 다음과 같은 움직임을 할 수 없다:

• 어떤 칸에서 묘비로 이동하는 움직임
• 묘비, 또는 귀신 구멍칸에서 주변 칸으로 이동하는 움직임
• 묘지 출구에서 주변 칸으로 이동하는 움직임

출력의 우선순위에도 신경을 쓰자:

1. 상근이가 끝없이 과거로 돌아갈 수 있다면 Never 출력
2. 그렇지 않고, 상근이가 묘지를 탈출할 수 없다면 Impossible 출력
3. 그렇지 않다면 묘지 탈출까지의 최단시간을 출력

위의 출력우선순위는 원문을 참고하였다.

이런 내용을 주의하여 구현한다면 이 문제를 해결할 수 있을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

struct edge {
	int x, y;
	ll d;
	edge(int x, int y, ll d) {
		this->x = x, this->y = y, this->d = d;
	}
};

vector<edge> edges;
int field[30][30]; // 2: 묘비
ll dist[900];

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

	int R, C; cin >> C >> R;
	while (R) {
		edges.clear();
		memset(field, 0, sizeof(field));

		int G; cin >> G;
		while (G--) {
			int r, c; cin >> c >> r;
			field[r][c] = 2;
		}

		int E; cin >> E;
		while (E--) {
			int r1, c1, r2, c2, d; cin >> c1 >> r1 >> c2 >> r2 >> d;
			edges.emplace_back(edge(r1 * C + c1, r2 * C + c2, d));
			field[r1][c1] = 1;
		}

		field[R - 1][C - 1] = 3;
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (field[r][c]) continue;
				if (r > 0) {
					if (!(field[r - 1][c] == 2)) edges.emplace_back(edge(r * C + c, (r - 1) * C + c, 1));
				}
				if (r < R - 1) {
					if (!(field[r + 1][c] == 2)) edges.emplace_back(edge(r * C + c, (r + 1) * C + c, 1));
				}
				if (c > 0) {
					if (!(field[r][c - 1] == 2)) edges.emplace_back(edge(r * C + c, r * C + c - 1, 1));
				}
				if (c < C - 1) {
					if (!(field[r][c + 1] == 2)) edges.emplace_back(edge(r * C + c, r * C + c + 1, 1));
				}
			}
		}

		int RC = R * C;
		dist[0] = 0;
		for (int i = 1; i < RC; i++) dist[i] = 1000000000;
		for (int i = 1; i < RC; i++) {
			for (auto e : edges) {
				if (dist[e.x] < 1000000000) dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
			}
		}

		bool chk = 1;
		for (auto e : edges) {
			if (dist[e.x] < 1000000000) {
				if (dist[e.y] > dist[e.x] + e.d) chk = 0;
			}
		}

		if (chk) {
			if (dist[RC - 1] == 1000000000) cout << "Impossible\n";
			else cout << dist[RC - 1] << '\n';
		}
		else cout << "Never\n";

		cin >> C >> R;
	}
}