(Python) - BOJ(17086번) : 아기 상어 2

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

17086번: 아기 상어 2

---

• 문제 : 

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

 

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

 

안전 거리가 가장 큰 칸을 구해보자. 

 

 

 

---

• 풀이 :

모든 아기 상어의 위치에서 (map[i][j] == 1 일때) bfs로 탐색을 시작하며 거리를 1씩 증가시킨다. 탐색을 시작한 아기 상어로부터 다른 아기 상어까지의 코스트들 중 max값을 리턴하고, 이 값을 모든 아기 상어에 대해서 최대로 갱신한다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
dx = [0, 0, 1, -1, -1, -1, 1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
 
def bfs(x, y):
    visit = [[0]*M for _ in range(N)]
    q = deque()
    visit[x][y] = 1
    q.append([x, y, 0])
 
    while q:
        x, y, cost = q.popleft()
        if space[x][y]:
            return cost
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny]:
                    visit[nx][ny] = 1
                    q.append([nx, ny, cost + 1])
 
if __name__ == '__main__':
    N,M = map(int,input().split())
    space = [list(map(int,input().split())) for _ in range(N)]
    ans  = 0
    for i in range(N):
        for j in range(M):
            if space[i][j] != 1:
                ans = max(ans,bfs(i,j))
    print(ans)