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

💡 방법은 비교적 쉽게 떠올렸지만, 시간이 꽤 오래 걸린 문제

문제

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

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

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

입력

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

출력

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

풀이 방법

1. 시간이 5000ms 가 넘게 나온 방법

처음 생각한 풀이이다.

모든 0인 칸에 대해서 검사를 진행한다. 주변 8칸을 돌면서 1이 나오지 않는다면 방문 여부를 나타내는 배열에 +1만큼을 더해준다.

만약 1이 나올 경우(아기상어 발견) 해당 칸의 방문여부 배열의 값에서 1을 빼서 리턴한다.

코드

# 안전 거리 : 칸에서 가장 가까운 아기상어와의 거리
# 거리 : 시작 칸에서 목표 칸까지 가기 위해 지나야 하는 칸의 수
# 8방향 이동 가능(대각선 포함)
# n행 m열
from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

direction = [(0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1), (1, -1), (1, 0), (1, 1)]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited = [[0] * m for _ in range(n)]
    visited[x][y] = 1
    visited_cnt = 1
    while queue:
        px, py = queue.popleft()
        # print(px, py)
        for dx, dy in direction:
            nx = px + dx
            ny = py + dy
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
                # print('상어', graph[nx][ny])
                # print('거리', visited[px][py])
                visited[nx][ny] = visited[px][py] + 1
                queue.append((nx, ny))
                if graph[nx][ny] == 1:
                    return visited[nx][ny]-1

dist = []
for i in range(n):
    for j in range(m):
        if graph[i][j] != 1:
            dist.append(bfs(i, j))

print(max(dist))