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

17086 아기 상어 2

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

두 아기 상어와 안전거리의 최댓값을 구하는 문제이다.

이때 안전거리는 각 좌표에서 아기 상어와 떨어진 거리이며 BFS를 사용하여 각 좌표에서 떨어진 상어와의 거리를 구해서 거리의 최댓값을 구하면 된다.

 

1. 상어의 위치에 대한 map을 입력받는다.

2. map에 상어가 존재하는 좌표를 모두 큐에 넣는다.

3. 각 상어의 위치부터 BFS를 진행하면서 상어가 존재하지 않는 좌표(0)인 경우 이동거리를 맵에 저장한다.

4. map을 완전탐색하여 맵에 저장된 최댓값이 안전거리의 최댓값이 되는데 1부터 시작했기 때문에 최댓값에서 1을 빼줘야 한다.

3. 코드

#include <iostream>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;
//BFS 사용
//각 좌표에서 아기상어와 떨어진 거리가 안전거리
int n, m, ret;
int map[51][51];
//대각선까지 방향설정
const int dr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
//안전거리를 구하기 위한 구조체
struct Pos
{
	int r, c;
};
queue<Pos> q;
int BFS()
{
	while (!q.empty())
	{
		Pos curr = q.front();
		q.pop();
		Pos next;
		for (int i = 0; i < 8; ++i)
		{
			next.r = curr.r + dr[i];
			next.c = curr.c + dc[i];
			if (next.r < 0 || next.r >= n || next.c < 0 || next.c >= m)
				continue;
			//빈칸인 경우
			if (!map[next.r][next.c])
			{
				//구한 안전거리의 좌표를 넣는다.
				q.push(next);
				//이때 좌표값은 현재 거리+1
				map[next.r][next.c] = map[curr.r][curr.c] + 1;
			}
		}
	}
	//안전거리의 최댓값을 구함
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (ret < map[i][j])
				ret = map[i][j];
		}
	}
	//상어의 위치인 1부터 시작했으므로 1을 빼준다
	return ret - 1;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> map[i][j];
			//상어가 있는 위치인 1부터 시작한다.
			if (map[i][j])
				q.push({ i, j });
		}
	}
	cout << BFS() << "\n";
	return 0;
}

4. 시간 복잡도

BFS 알고리즘을 이용하였으며 O(n*m)의 시간 복잡도를 가진다.

5. 결과