[백준] 17086 : 아기 상어 2 python

 

그래프를 입력받을 때 상어가 있는 위치의 행,열 위치를 큐에 삽입한다.

 

큐에서 상어의 위치를 하나씩 꺼내면서

주변에 0(아직 탐색하지 않은 물)이 있으면 거리값을 1 증가시키고 그걸 그래프에 저장한 뒤

BFS 탐색을 하는 식으로 문제를 풀었다.

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    while shark:
        x,y = shark.popleft()
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if graph[nx][ny]==0:
                    shark.append((nx,ny))
                    graph[nx][ny] = graph[x][y]+1

# 방향벡터
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]

# 그래프의 크기를 입력받음
N,M = map(int,input().split())
graph = []
# 상어의 위치를 저장할 큐
shark = deque()

# 그래프의 정보를 한 줄씩 입력받음
for i in range(N):
    tmp = list(map(int,input().split()))
    for j in range(M):
    	# 상어의 위치를 큐에 저장
        if tmp[j] == 1:
            shark.append((i,j))
    # 한줄씩 입력받은 그래프 정보를 이어붙임
    graph.append(tmp)

bfs()

# graph는 2차원 리스트이므로 각 행의 최대값들을 구하고
# 그 값들의 최대값을 다시 구한 뒤 -1을 함
print(max(map(max,graph))-1)