17086번: 아기 상어 2

메모리

시간

1228 KB

0 ms

문제 풀이

n * m 크기의 pool이 있고 1마리 이상의 상어가 있다.

최대 안전 거리를 구하는 문제로 처음 방문할때는 이전 인덱스 + 1을 주고 이미 인덱스가 더 큰 수일 때에는 최대 안전 거리를 바꿔주는 부분을 어떻게 구현할지 고민했다.

그 부분은 vis 배열 초기화를 시켜줄때 0일땐 100으로 초기화 해주는 것으로 해결했고 상어가 있는 칸이면 0으로 초기화 해주었다.

큐에 상어의 위치값을 넣어주며 다음 방문할 칸이 유효한 값이라면 해당 x,y 값을 넣어주며 돌린다.

모든 칸을 방문 했을때 저장한 각 칸의 최대 안전거리이다.

Code

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	int pool[51][51];
	int vis[51][51];
	int mx[8] = {1, 1, 1, 0, -1, -1, -1, 0};
	int my[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
	int result = 0;
	int n, m;
	scanf("%d%d", &n, &m);
	queue <pair<int,int> > que;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &pool[i][j]);
			if (pool[i][j] == 1)
			{
				que.push({i,j});
				vis[i][j] = 0;
			}
			else
				vis[i][j] = 100;
		}
	}

	while (!que.empty())
	{
		int x = que.front().first;
		int y = que.front().second;
		que.pop();
		for (int j = 0; j < 8; j++)
		{
			int m_x = x + mx[j];
			int m_y = y + my[j];

			if (m_x < n && m_x >= 0 && m_y < m && m_y >= 0 
					&& vis[m_x][m_y] > vis[x][y] + 1)
			{
				if (pool[m_x][m_y] == 0)
					vis[m_x][m_y] = vis[x][y] + 1;
				que.push({m_x, m_y});
				result = max(result, vis[m_x][m_y]);
			}
		}
	}
	printf("%d\\n", result);	
	
	return 0;
}