Search
Duplicate

아기 상어 2

주차
17
문제번호
17086
언어
C++
티어
실버
유형
BFS
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사