[Silver II] 아기 상어 2 - 17086

문제 링크

성능 요약

메모리: 114200 KB, 시간: 152 ms

분류

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색

제출 일자

2025년 5월 28일 17:20:52

문제 설명

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

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

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

입력

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

출력

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

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/17086
 
from collections import deque
 
n, m = map(int, input().split())
 
space = [list(map(int, input().split())) for _ in range(n)]
 
dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]
 
dist = [[-1] * m for _ in range(n)]
 
q = deque()
 
for i in range(n):
    for j in range(m):
        if space[i][j] == 1:
            q.append((i, j))
            dist[i][j] = 0
 
 
while q:
    y, x = q.popleft()
    for d in range(8):
        ny, nx = y + dy[d], x + dx[d]
        if 0 <= ny < n and 0 <= nx < m and dist[ny][nx] == -1:
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))
 
 
if any(i2 == -1 for i in dist for i2 in i ):
    exit(0)
 
ans = max(map(max, dist))
 
print(ans)