Memo
로직 설명
•
처음에는 모든 빈 칸에 대해서 상어의 거리의 최소값을 구하고 ,그 값들 중에 최대값을 고르는 방법을 생각해 코드를 작성했습니다. 이때의 시간복잡도는 (모든 칸을 순회하는데 걸리는 시간 N*M) 과 (모든 칸에 상어가 없는 경우에 모든 칸을 순회하므로 N*M)을 곱하여 O((N * M)^2) 입니다.
•
hyospark님의 풀이를 참고하여, 상어의 좌표를 큐에 넣고 상어가 이동할 수 있는 거리를 넓혀가며 안전거리의 최대값을 구하는 방법으로 수정했습니다. 이 때의 시간 복잡도는 O(N * M) 입니다. (8방향 조사하므로 원래는 8도 곱해야함)
이전 코드
Code
제출 날짜
@4/23/2021
메모리
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);
}
C++
복사