[Python] 백준 17086번 아기 상어2

문제

17086번: 아기 상어 2

입력

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

출력

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

입력 예제

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

출력 예제

2

2

문제 풀이

• 그래프의 값이 0인경우 값이 1인 곳 까지의 최단거리를 탐색해야 하므로, 상어가 있는 곳에서부터 탐색 진행
• 상어가 있는 곳의 좌표를 큐에 넣고, 8방향으로 탐색을 진행해가며, 거리 값 업데이트
• 모든 연산을 마친 후, 그래프에는 거리 값이 저장되어있으므로 최대 값 출력 
  • 이 때, 상어가 있는 곳의 값은 1이었으므로, 거리가 0이 아닌 1부터 시작했기 때문에 1을 다시 빼준 후 출력해야 정답 판정을 받을 수 있다.

코드

from collections import deque
dy = [-1,-1,-1,0,0,1,1,1]
dx = [-1,0,1,-1,1,-1,0,1]
n, m = map(int,input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

def bfs():
    while queue:
        y,x = queue.popleft()
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((ny,nx))
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i,j))

bfs()
print(max(map(max,graph)) - 1)