[백준 17086번] 아기 상어 2 (C++)

문제링크 : https://www.acmicpc.net/problem/17086

 

#include <bits/stdc++.h> 
using namespace std;

int n, m, result = 0;

queue<pair<int, int>> q;
int arr[52][52];
int dx[8] = { 0, 0, -1, 1, -1, -1, 1, 1 };    //1 좌, -1 우
int dy[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };  //1 상, -1 하

void bfs()
{
	while (!q.empty())
	{
		int x = q.front().first, y = q.front().second; q.pop();
		for (int i = 0; i < 8; i++)
		{
			int nx = x + dx[i];   //다음 x 좌표    
			int ny = y + dy[i];   //다음 y 좌표
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) { continue; } //범위 조건
			if (!arr[nx][ny])
			{
				q.push({ nx, ny });           //새로운 좌표 입력
				arr[nx][ny] = arr[x][y] + 1;  //1을 계속 더해줌으로서 거리 증가
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j]) q.push({ i, j });  //아기 상어가 있는 위치만 입력
		}
	}

	bfs();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			result = max(result, arr[i][j]);  //거리 최댓값 저장
		}
	}
	cout << result-1;  //거리를 1로 시작했기에 1을 빼줘야함
	return 0;
}

아기 상어의 위치만 따로 큐에 저장하고 그 위치를 기준으로 거리를 증가시킨다. (거리를 1로 시작했기에 마지막에 1 뺴기)

배열에 입력 값이 0과 1뿐이므로 배열 1개만 가지고 계산해도 괜찮다.