[파이썬/python] 백준 - 17086 아기 상어 2

문제

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

---

문제 설명

1. N*M 크기의 공간에 아기 상어 여러 마리가 있다.
2. 안전거리는 현재 칸에서 아기 상어와 가장 가까운 거리를 말한다.
3. 인접한 8방향으로 이동이 가능하다.
4. 이 때 모든 칸을 기준으로 안전거리의 최댓값을 구한다.

 

---

풀이

단순 BFS 문제이다. 매 위치를 갱신하면서 다음 위치가 현재 위치 + 1 거리보다 크다면 갱신하도록 탐색했다.

1. 배열을 완전 탐색하여 상어의 위치를 전부 queue에 넣는다.
2. BFS을 진행한다.
   1. 만약 현재 위치 (y,x)에서 1을 더한 크기가 (ny,nx)의 안전거리보다 더 작다면 갱신한다.
   2. max_dist를 통해 갱신될 때 마다 최댓값을 갱신한다.
3. 결과를 출력한다. 

 

---

코드

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

n,m = map(int,input().split())

board = [list(map(int,input().split())) for _ in range(n)]
visited = [[INF for _ in range(m)] for _ in range(n)]
queue = deque([])

for y in range(n):
    for x in range(m):
        if board[y][x]:
            queue.append((y,x))
            visited[y][x] = 0

dy = [0,1,0,-1,1,1,-1,-1]
dx = [1,0,-1,0,1,-1,1,-1]

def bfs():
    max_dist = 0
    while queue:
        y,x = queue.popleft()
        
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny > n-1 or nx < 0 or nx > m-1:
                continue
            if  visited[y][x] + 1 < visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                queue.append((ny,nx))
                max_dist = max(max_dist,visited[ny][nx])
    return max_dist

print(bfs())

---

시간복잡도

• BFS의 시간복잡도는 $O(N*M)$이다.
• N,M은 최대 50이므로, 약 $O(50*50) = O(10^3)$의 시간복잡도가 소요된다.