💡 문제
N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.
어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
안전 거리가 가장 큰 칸을 구해보자.
입력
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.
출력
첫째 줄에 안전 거리의 최댓값을 출력한다.
💭 접근
이 문제는 간단한 BFS 문제로, 입력으로 주어진 모든 상어의 위치에서 모든 칸의 최소 거리를 구하고, 이 중 최댓값을 구하면 되는 문제이다.
- 먼저 입력으로 주어진 모든 상어의 위치를 큐에 넣는다.
for x in range(n):
for y in range(m):
if graph[x][y] == 1:
visited[x][y] = 0
q.append([x, y])- 큐에 입력된 각 상어의 위치를 시작으로 각 칸에 상어와 떨어진 거리를 구한다. 이때 각 칸은 모든 상어와 떨어진 거리의 최솟값을 저장한다.
while q:
x, y = q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] >= visited[x][y] + 1:
visited[nx][ny] = visited[x][y] + 1
q.append([nx, ny])- 마지막으로 모든 칸에 대해 최댓값을 구한다.
ans = 0
for i in range(n):
ans = max(ans, max(visited[i]))📒 코드
from collections import deque
def bfs():
q = deque()
for x in range(n):
for y in range(m):
if graph[x][y] == 1:
visited[x][y] = 0
q.append([x, y])
while q:
x, y = q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] >= visited[x][y] + 1:
visited[nx][ny] = visited[x][y] + 1
q.append([nx, ny])
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[float('inf') for _ in range(m)] for _ in range(n)]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
bfs()
ans = 0
for i in range(n):
ans = max(ans, max(visited[i]))
print(ans)💭 후기
오랜만에 간단한 BFS 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/17086
精進 "정성을 기울여 노력하고 매진한다"