[17086] 아기상어 2 in python

 

전형적인 bfs 함수 문제!

 

문제에서 주어진 예제의 맵은

아래와 같다.

 

0은 벽,

1은 상어

 

이 문제에서 원하는 것은

안전거리가 가장 큰 칸을 구하는 것

 

안전거리가 무엇을 의미하느냐!

해당 칸과 가장 가까이 있는 아기 상어와의 거리를 의미한다.

 

상어가 1마리면 구하기 쉬웠을 텐데

상어가 여러마리 존재하니까

그걸 어떻게 해결해야 하느냐가 관건이었던 문제다.

 

 

 

bfs를 이용하여

처음에 상어의 위치들을 먼저 큐에 넣고 시작한다.

 

(1,3)

(3,1)

(5,4)

를 각각 큐에 먼저 넣는다.

 

그리고 나서 (1,3) 위치에 있는 상어 주변 8방향을 살펴보고

0인 곳은 array[1][3]+1을 더해준 값을 넣어준다.

 

0이 아니면 패쓰!

 

이런식으로 하면 된다!

(간단)

 

dfs로 풀 수 없는 이유는

상어가 여러 마리 존재하기 때문이다!

 

상어가 한 마리면 가능할테지만..

1번 상어와는 멀어졌다 쳐도 2번 상어와 가까워지면

2번 상어와의 거리로 다시 리셋해줘야하는데

그렇게 되면 과정이 매우 복잡해진다!

 

 

# 아기 상어 2
from collections import deque

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]

# 상,상우,우,하우,하,하좌,좌,상좌
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

queue = deque()
for i in range(n):
    for j in range(m):
        if array[i][j] == 1:
            queue.append((i, j))

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not array[nx][ny]:
                    queue.append((nx, ny))
                    array[nx][ny] = array[x][y] + 1
bfs()
print(max(map(max,array))-1)