[백준/BOJ] 백준 3860번 : 할로윈 묘지

www.acmicpc.net/problem/3860

3860번: 할로윈 묘지

그래프를 만들고 벨만 포드 알고리즘을 이용해 문제를 해결했다. 벨만 포드 알고리즘에서 here이 묘비인 경우와, here로 아직 오는 방법이 없을 때를 고려한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int w, h;
int g;
int e;
vector<pair<int, pair<int, int>>> adj[30][30]; //걸리는 시간과 위치
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int check_g_stone[30][30];
int node_num;

void Pre()
{
	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 30; j++)
		{
			adj[i][j].clear();
			check_g_stone[i][j] = 0;
		}
}

//그래프 만들기
void Make_adj()
{
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			pair<int, int> here = make_pair(i, j);

			//here이 묘비일때
			if (check_g_stone[here.first][here.second] == 1)
				continue;

			//here이 출구일때
			if (here.first == h - 1 && here.second == w - 1)
				continue;

			//접한 4곳을 그래프로 연결
			for (int k = 0; k < 4; k++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[k][0], here.second + dxdy[k][1]);

				if (there.first >= 0 && there.first < h && there.second >= 0 && there.second < w)
				{
					if (check_g_stone[there.first][there.second] == 1) //there이 묘비일때
						continue;

					adj[here.first][here.second].push_back(make_pair(1, make_pair(there.first, there.second)));
				}
			}
		}
}

//벨만포드 알고리즘 사용
int Solve(pair<int, int> start, pair<int, int> dest)
{
	vector<vector<int>> upper(h, vector<int>(w, 987654321));

	upper[start.first][start.second] = 0;

	bool update;

	for (int i = 0; i < node_num; i++)
	{
		update = false;

		for (int j = 0; j < h; j++)
			for (int k = 0; k < w; k++)
			{
				pair<int, int> here = make_pair(j, k);

				if (check_g_stone[here.first][here.second] == 1)
					continue;

				if (upper[here.first][here.second] == 987654321) //아직 here에 오는 방법이 없을때
					continue;

				for (int l = 0; l < adj[here.first][here.second].size(); l++)
				{
					pair<int, int> there = adj[here.first][here.second][l].second;
					int cost = adj[here.first][here.second][l].first;

					if (upper[there.first][there.second] > upper[here.first][here.second] + cost)
					{
						upper[there.first][there.second] = upper[here.first][here.second] + cost;
						update = true;
					}

				}
			}

		if (update == false)
			break;
	}

	if (update == true)
		return -987654321;

	return upper[dest.first][dest.second];
}

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

	while (1)
	{
		Pre();

		cin >> w >> h;

		if (w == 0 && h == 0)
			break;

		node_num = w * h;

		cin >> g;

		node_num -= g;

		for (int i = 0; i < g; i++)
		{
			int x, y;
			cin >> x >> y;

			check_g_stone[y][x] = 1;
		}

		Make_adj();

		cin >> e;

		for (int i = 0; i < e; i++) //귀신 구멍 부분은 이전에 만든 그래프에서 수정 
		{
			int x1, y1, x2, y2, t;

			cin >> x1 >> y1 >> x2 >> y2 >> t;

			adj[y1][x1].clear(); //이전에 만든것 삭제
			adj[y1][x1].push_back(make_pair(t, make_pair(y2, x2)));
		}

		int result = Solve(make_pair(0, 0), make_pair(h - 1, w - 1));

		if (result == -987654321)
			cout << "Never" << "\n";
		else if (result == 987654321)
			cout << "Impossible" << "\n";
		else
			cout << result << "\n";
	}

	return 0;
}