3860 할로윈 묘지 (라이브러리x)

1. 문제

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

3860번: 할로윈 묘지

 

 2. 코드

#include <iostream>
#include <cstring>
#define INF 987654321

using namespace std;

int dist[1000];
bool stone[35][35];
bool ghost[35][35];

struct edge {
	int from, to, cost;
}E[5000];

int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };

int main() {
	while (1) {
		int w, h;
		cin >> w >> h;
		if (w == 0 && h == 0) break;

		memset(stone, false, sizeof(stone));
		memset(ghost, false, sizeof(ghost));
		for (int i = 0; i < w*h; i++) {
			dist[i] = INF;
		}
		dist[0] = 0;

		int g;
		cin >> g;
		for (int i = 0; i < g; i++) {
			int x, y;
			cin >> y >> x;
			stone[x][y] = true;
		}

		int edgeIdx = 0;

		int e;
		cin >> e;
		for (int i = 0; i < e; i++) {
			int fx, fy, tx, ty, t;
			cin >> fy >> fx >> ty >> tx >> t;
			E[edgeIdx].from = (fx * w + fy);
			E[edgeIdx].to = (tx * w + ty);
			E[edgeIdx++].cost = t;
			ghost[fx][fy] = true;
		}
		
		for (int x = 0; x < h; x++) {
			for (int y = 0; y < w; y++) {
				if (stone[x][y] || ghost[x][y] || (x == h-1 && y == w-1)) continue;	//묘비이거나 귀신구멍이면 다시
				for (int d = 0; d < 4; d++) {
					int nx = x + dir[d][0];
					int ny = y + dir[d][1];
					if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
					if (stone[nx][ny]) continue;

					E[edgeIdx].from = (x * w + y);
					E[edgeIdx].to = (nx * w + ny);
					E[edgeIdx++].cost = 1;
				}
			}
		}

		int v = w * h - g;
		for (int i = 0; i < v - 1; i++) {
			for (int j = 0; j < edgeIdx; j++) {
				if (dist[E[j].from] != INF && dist[E[j].to] > dist[E[j].from] + E[j].cost) {
					dist[E[j].to] = dist[E[j].from] + E[j].cost;
				}
			}
		}

		bool cycle = false;
		for (int j = 0; j < edgeIdx; j++) {
			if (dist[E[j].from] != INF && dist[E[j].to] > dist[E[j].from] + E[j].cost) {
				cycle = true;
				break;
			}
		}

		if (cycle) cout << "Never\n";
		else if (dist[w*h - 1] == INF) cout << "Impossible\n";
		else cout << dist[w*h - 1] << "\n";
	}
}

 

3. 후기

알고리즘 : 벨만포드

2차원 배열로 하는 방법이 있을 것 같은데 떠오르지 않아서 1차원 배열로 풀었다. 모든 정점의 개수는 w*h-g로 구할 수 있고, 간선의 개수는 간선을 추가할 때마다 1씩 늘려가며 구했다. 

주의할 점은 간선을 구할 때 출구인 (x == h-1 && y == w-1)에서는 간선을 만들면 안된다.