[백준] 17086번: 아기상어2- 파이썬

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

17086번: 아기 상어 2

문제

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

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

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

 

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.

 

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

 

풀이

BFS 탐색 문제이지만 처음에는 그냥 그리디(?)로 풀었는데 운이 좋게도 시간초과가 안났다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]

baby_sharks = [(r,c) for r in range(N) for c in range(M) if MAP[r][c] == 1]

answer = 0
for row in range(N):
    for col in range(M):
        if (row,col) in baby_sharks: continue
        distance = [max(abs(row-shark[0]), abs(col-shark[1])) for shark in baby_sharks]
        answer = max(answer, min(distance))

print(answer)

 

하지만 BFS로 풀면 훨씬 빠르다! 

안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이기 때문에 상어들의 위치로부터 BFS 탐색을 하면서 거리를 계산하고 그 중 가장 큰 값을 구하면 된다.

 

 

답안 코드

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

N, M = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]

row_moves=[1,1,1,0,0,0,-1,-1,-1]
col_moves=[1,0,-1,1,0,-1,1,0,-1]

distance = [[-1]*M for _ in range(N)]
baby_sharks = [(r,c,0) for r in range(N) for c in range(M) if MAP[r][c] == 1]

answer = 0
queue = deque(baby_sharks)

while queue:
    row, col, dist = queue.popleft()

    for mr, mc in zip(row_moves, col_moves):
        new_row, new_col, new_dist = row+mr, col+mc, dist+1
        if 0<=new_row<N and 0<=new_col<M:
            if distance[new_row][new_col] == -1:
                distance[new_row][new_col] = new_dist
                queue.append((new_row, new_col, new_dist))
                if answer < new_dist:
                    answer = new_dist

print(answer)