[Python] 백준 17086 아기 상어 2

 

문제 분석

• NxM 크기의 공간에 아기 상어
• 인접한 8 방향으로 이동 가능

 

풀이

• 최단 거리 → bfs
• 아기 상어 간의 거리를 구하고, 현재의 최대 길이와 비교
  
  
• 안전 거리를 어떻게 구할 수 있는가
  • 모든 칸에서 부터 bfs를 탐색해 상어를 만날 때까지의 거리를 찾을 수도 있지만
  • 상어의 위치부터 시작해 한 칸씩 bfs를 탐색하며 상어와의 거리를 기록하는 것이 더 효율적
• 단, 상어가 있는 칸을 1로 시작했기 때문에 최댓값 거리에서 -1을 해주어야 한다.
  
  

시간 복잡도

한 번 탐색된 정점은 다시 탐색하지 않기 때문에 O(NM) 개의 정점을 탐색힌다.
한 정점에서 8가지 방향으로 이동할 수 있기 때문에 8*O(NM)의 시간복잡도가 소요된다.
여기서 상수 배수를 무시하면 O(NM)

 

코드 설계

• input
• 상어의 위치를 큐에 넣고
• 상어로부터의 거리를 탐색하는 bfs 코드 구현
• 거리들 중 최댓값 확인 → 정답 출력

 

정답 코드

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

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

shark = deque()

dh = [-1, 1, 0, 0, -1, -1, 1, 1]
dw = [0, 0, -1, 1, -1, 1, -1, 1]
max_distance = 0

for i in range(n) :
    for j in range(m) :
        if g[i][j] == 1 :
            shark.append((i, j))

def bfs() :
    while shark :
        h, w = shark.popleft()

        for k in range(8) :
            nh = h + dh[k]
            nw = w + dw[k]

            if nh < 0 or nh >= n or nw < 0 or nw >= m :
                continue
            if g[nh][nw] == 0:
                shark.append((nh, nw))
                g[nh][nw] = g[h][w] + 1

bfs()
ans = 0

for i in range(n) :
    for j in range(m) :
        ans = max(ans, g[i][j])

print(ans-1)