[BOJ] 17086번 아기 상어2 파이썬

문제

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

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

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

입력

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

출력

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

풀이

#bfs

상어로부터의 거리를 계산해주기 위해 상어가 있는 칸을 기준으로 bfs를 실행해주었으며 탐색을 진행하면서는 빈 칸들을 큐에 넣어가며 안전 거리를 계산해주었다.

이때 저장되어 있는 안전거리가 0인 경우에는 이전 칸+1로 갱신시켜주었고 안전거리가 0이 아닌 경우에는 기존 값과 비교하여 최소값을 저장했다. 이 연산을 위해 삼항 연산자를 이용했는데 파이썬에서 처음 사용해봐서 방법을 찾아봤다.

[true_value] if [condition] else [false_value]

그리고 탐색을 모두 마치고 마지막에 dist 배열에서 최대값을 구함으로써 최대 안전 거리를 구해주었다.

뭔가 파이썬은 반복문을 사용하지 않고도 배열의 최대값 최소값을 구하는 방법이 있을 것 같아 찾아봤다.

#1차원 배열
min(arr)
max(arr)

#2차원 배열
min(map(min, arr))
max(map(max, arr))

코드

from collections import deque

N, M = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, 1, 1, -1]

result = 0


dist = [[0] * M for _ in range(N)]


def bfs(x, y):
    q = deque([(x, y)])
    visited = [[False] * M for _ in range(N)]
    visited[x][y] = True

    while q:
        px, py = q.popleft()

        for i in range(8):
            nx, ny = px + dx[i], py + dy[i]

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if arr[nx][ny] == 0:
                    q.append((nx, ny))
                    dist[nx][ny] = dist[px][py]+1 if not dist[nx][ny] else min(dist[px][py]+1, dist[nx][ny])

                    visited[nx][ny] = True


for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            bfs(i, j)


print(max(map(max, dist)))