[Python] 백준 17086 아기 상어 2

1. 문제 링크

https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

---

2. 문제 요약

• 안전거리 최댓값 구하기

---

3. 아이디어 정리

• bfs 탐색을 통해 최단 거리 구하기

---

4. 문제 풀이

4-1. 내 풀이

import sys
from collections import deque
dx = [-1, -1, -1, 0, 1, 0, 1, 1]
dy = [-1, 0, 1, 1, 1, -1, 0, -1]

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dq = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:  # 상어가 있는 위치에서 탐색하기 위해 
            dq.append([i, j])

result = 0
# 상어 있는 위치 기준으로 최단 거리 구하기 
while dq:
    x, y = dq.popleft()
    for d in range(8):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if graph[nx][ny] != 0:
            continue
        dq.append([nx, ny])
        graph[nx][ny] = graph[x][y] + 1
        result = max(result, graph[x][y] + 1)
print(result - 1)

 

---

5. 결론

• bfs 문제 중 최단거리 구하기와 동일한 문제