[boj : 16569] 화산쇄설류

www.acmicpc.net/problem/16569

16569번: 화산쇄설류

문제 : 지정된 시간에 화산이 터지고 이 화산은 인접한 칸에 점점 퍼진다. 이때 윤재상이 갈 수 있는 곳 중 가장 높은 고지대의 높이와 도달하기까지 시간을 구해라

 

해설 : "t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다."

이 말은 화산쇄설류가 인접한 칸으로 1초마다 점점 퍼진다는 이야기 입니다.

 

www.acmicpc.net/problem/4179

4179번: 불!

www.acmicpc.net/problem/3055

3055번: 탈출

만약 이 두문제를 아직 안푸셨으면 먼저 풀고 오세요!!!(반드시)

 

위 두문제와 로직은 같습니다. 다만 구현이 좀 더 복잡할 뿐이죠.

주의할 점은 미리 화산의 위치를 방문했다고 체크하면 안됩니다.(www.acmicpc.net/board/view/35528)

 

큐 2개, 화산의 위치, 화산쇄설류와 재상이의 방문 배열 을 사용했습니다.

화산의 위치와 시간을 처리해 주기 위해 vector 배열을 사용해 주었습니다.

 

#include<bits/stdc++.h>

using namespace std;

int n, m, v;
int board[110][110],mt[110][110];
int check1[110][110],check2[110][110],second[110][110];
vector<pair<int, int>> pos[210];

pair<int, int> bfs(int x, int y);

int main()
{	
	int x, y;
	int a, b, c;
	cin >> n >> m >> v;
	cin >> x >> y;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> board[i][j];
	for (int i = 0; i < v; i++) {
		cin >> a >> b >> c;
		pos[c].push_back({ a,b });
		mt[a][b] = 1;
	}	
	pair<int,int> ans = bfs(x, y);
	cout << ans.first << " " << ans.second;
	return 0;
}
pair<int, int> bfs(int x, int y)
{
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	queue<pair<int, int>> q1, q2;
	q2.push({ x,y });
	check2[x][y] = 1;

	for (pair<int, int> u : pos[0]) {
		q1.push(u);
		mt[u.first][u.second] = 1;
	}
	int cnt = 0;
	while (!q2.empty())
	{
		int size1 = q1.size();
		for (int s = 0; s < size1; s++) {
			pair<int, int> cur = q1.front();
			q1.pop();

			for (int i = 0; i < 4; i++) {
				int tx = cur.first + dx[i];
				int ty = cur.second + dy[i];

				if (tx <= 0 || tx > n || ty <= 0 || ty > m)continue;

				if (!check1[tx][ty] && !check2[tx][ty]) {
					check1[tx][ty] = 1;
					q1.push({ tx,ty });
				}
			}
		}		
		int size2 = q2.size();
		for (int s = 0; s < size2; s++) {
			pair<int, int> cur = q2.front();
			q2.pop();

			for (int i = 0; i < 4; i++) {
				int tx = cur.first + dx[i];
				int ty = cur.second + dy[i];

				if (tx <= 0 || tx > n || ty <= 0 || ty > m)continue;

				if (!check2[tx][ty] && !check1[tx][ty] && !mt[tx][ty]) {
					check2[tx][ty] = 1;
					second[tx][ty] = cnt + 1;
					q2.push({ tx,ty });
				}
			}
		}
		cnt++;		
		//폭발
		if (cnt <= 200) {
			for (pair<int, int> cur : pos[cnt]) {
				q1.push(cur);
				mt[cur.first][cur.second] = 1;
			}
		}
	}
	int ret = -1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (check2[i][j] && ret < board[i][j])
				ret = board[i][j], cnt = second[i][j];				
	return { ret,cnt };
}