[BOJ] 17086 아기상어 2 Python

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

17086번: 아기 상어 2

아기 상어 2

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

7106

3486

2601

47.420%

문제

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

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

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

입력

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

출력

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

풀이 코드

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

r, c = map(int, input().split())
graph = []
for i in range(r):
    graph.append(list(map(int, input().split())))

queue = deque()
for i in range(r):
    for j in range(c):
        if graph[i][j]==1:
            queue.append((i, j))
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, 1, 1, -1]
def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx, ny = x+dx[i], y+dy[i]
            if 0<= nx < r and 0<= ny < c and graph[nx][ny]==0:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx, ny))
bfs()
print(max(map(max, graph))-1)

간단한 bfs 문제다. 

2차원 배열에서 최댓값을 출력할 때

max(map(max, graph)) 잊지 말자 !