17086번: 아기 상어 2

Memo

로직 설명

• 처음에는 모든 빈 칸에 대해서 상어의 거리의 최소값을 구하고 ,그 값들 중에 최대값을 고르는 방법을 생각해 코드를 작성했습니다. 이때의 시간복잡도는 (모든 칸을 순회하는데 걸리는 시간 NM) 과 (모든 칸에 상어가 없는 경우에 모든 칸을 순회하므로 NM)을 곱하여 O((N * M)^2) 입니다.

• hyospark님의 풀이를 참고하여, 상어의 좌표를 큐에 넣고 상어가 이동할 수 있는 거리를 넓혀가며 안전거리의 최대값을 구하는 방법으로 수정했습니다. 이 때의 시간 복잡도는 O(N * M) 입니다. (8방향 조사하므로 원래는 8도 곱해야함)

• 이전 코드

Code

제출 날짜

2021/04/23

메모리

2160 KB

시간

0 ms

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
#include <algorithm>

int N, M;
int g_map[51][51];
std::queue<std::pair<int, int> >q;
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int ans;

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N >> M;
	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < M ; j++)
		{
			std::cin >> g_map[i][j];
			if (g_map[i][j])
				q.push({i, j});
		}
}

void bfs()
{
	int qy, qx, nx, ny;

	while (!q.empty())
	{
		qy = q.front().first;
		qx = q.front().second;
		q.pop();
		for (int i = 0 ; i < 8 ; i++)
		{
			ny = qy + dy[i];
			nx = qx + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M)
				continue ;
			if (!g_map[ny][nx])
			{
				q.push({ny, nx});
				g_map[ny][nx] = g_map[qy][qx] + 1;
				if (ans < g_map[qy][qx])
					ans = g_map[qy][qx];
			}
		}
	}
}

void solve()
{
	bfs();
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}