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

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

17086번: 아기 상어 2

 

Problem

• N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다.
• 안전 거리가 가장 큰 칸을 구해보자. 

조건

• 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
• 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.

SOL

간단한 BFS 문제라고 생각했지만, 생각보다 짚어야할 곳이 많은 문제이다.

 

shark가 있는 board에서, 빈칸을 기준으로 탐색을 돌아줄건지, 상어를 기준으로 돌아줄건지 생각해보자.

• shark가 있는 board에서 빈칸을 기준으로 탐색을 한다면, 빈칸의 모든 좌표를 deque에 넣어줘야하고, 상어만 생각한다면, 상어들의 좌표를 deque에 넣어줘야할거임.
• 이 문제에서는, 상어는 최소 몇개, 빈칸은 최소 1개는 있다는 말을 보니까, 둘 다 상관없을 거 같다.
• 따라서, 뭘 기준으로 하던지 상관을 없을거 같다. (단, 주의해할게, 빈칸을 찾을때마다/상어를 찾을때마다 bfs를 돌아주는 만행을 저지르지말자). 그럼 더하기 관계보다, 곱하기 관계가 된다.

시간복잡도를 생각해주자

• 상어를 기준으로 해주겠다.
• 상어를 찾는 과정 O(NM) + BFS(O(NM)) + 최댓값 찾는과정 O(NM) = 3O(NM) => O(NM)

어떤식으로 dist를 구해줄건지 생각해보자.

• board에 바로 거리를 기록해줘서, 방문배열을 대신해서 쓰자. board에서 기록이 되어있으면, 그 곳은 건드리면 안된다. 
• (왜냐하면, BFS이기 때문에, 상어에서의 최단거리가 항상 기록되기 때문이다)
• 그리고, 방문배열을 돌아주면서, max값을 갱신시켜주자.

 

# 아기 상어 뚜루두뚜뚜
import sys
from collections import deque
input= sys.stdin.readline
N,M =map(int,input().split())
dx=[0,1,0,-1,1,1,-1,-1]
dy=[1,0,-1,0,1,-1,-1,1]

board=[list(map(int,input().split())) for _ in range(N)]
dq=deque()

def bfs():
    while dq:
        y,x=dq.popleft()
        for k in range(8):
            ny=y+dy[k]
            nx=x+dx[k]
            if ny<0 or ny>=N or nx<0 or nx>=M:
                continue
            #이미, board에 기록되어있음
            if board[ny][nx] ==0:
                dq.append((ny,nx))
                board[ny][nx] = board[y][x] +1
    return

for i in range(N):
    for j in range(M):
        if board[i][j] ==1:
            dq.append((i,j))

bfs()

dist=-1
for i in range(N):
    for j in range(M):
        dist =max(dist,board[i][j])

print(dist-1)