[백준] 17086번 - 아기 상어 2 / C++

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전거리가 가장 큰 칸을 구해보자. 

 

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈칸, 1은 아기 상어가 있는 칸이다. 빈칸의 개수가 한 개 이상인 입력만 주어진다.

 

출력

첫째 줄에 안전거리의 최댓값을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int N;
int M;
int space[51][51];
int visit[51][51];
vector<pos> shark;

bool in_range(pos p)
{
	if (p.r < 1 || p.r > N || p.c < 1 || p.c > M)
		return false;
	return true;
}

int bfs()
{
	queue<pos> q;
	pos curr, next;
	int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
	int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
	int i, res = 0;

	for (i = 0; i < shark.size(); i++)
	{
		q.push(shark[i]);
	}
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		res = max(res, visit[curr.r][curr.c]);
		for (i = 0; i < 8; i++)
		{
			next.init(curr.r + dr[i], curr.c + dc[i]);
			if (!in_range(next))
				continue;
			if (space[next.r][next.c])
				continue;
			if (visit[next.r][next.c])
				continue;
			visit[next.r][next.c] = visit[curr.r][curr.c] + 1;
			q.push(next);
		}
	}
	return res;
}

int main()
{
	int i, j;
	pos p;

	cin >> N >> M;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= M; j++)
		{
			cin >> space[i][j];
			if (space[i][j])
			{
				p.init(i, j);
				shark.push_back(p);
			}
		}
	}
	cout << bfs() << endl;
	return 0;
}

 

상어가 있는 곳에서부터 BFS를 시작한다. 상어가 있는 칸의 안전거리는 0이며 인접한 칸에 대해 거리를 저장한다. 좌표가 범위를 벗어나거나 상어가 있는 곳인 경우 패스한다. 또한, 이미 방문한 적이 있다면 그때 가장 가까운 아기 상어와의 거리가 이미 저장되었으므로 패스한다. 각 좌표에 대한 안전거리를 확인해 최댓값을 갱신하고, 탐색을 마친 후에는 확인된 최댓값을 리턴한다.

 

링크

17086번: 아기 상어 2

inbdni/Baekjoon