백준 17086번 아기상어 2 | python | bfs

문제

링크

풀이

문제에서 제시한 그대로 풀이해보자.
배열의 모든 원소에 대하여 bfs()를 진행하여 반환된 최소 안전 거리의 최댓값을 출력하면 쉽게 답을 구할 수 있다.

그 코드는 아래와 같다.

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().strip().split())

arr = [list(map(int, input().split())) for _ in range(n)]


# 인접 방향(대각선 포함)
d = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]


def bfs(y, x):
    q = deque()
    q.append((y, x))
    visited = [[0] * m for _ in range(n)]
    isShark = 0  # flag
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y = y + dy
            X = x + dx
            if 0 <= X < m and 0 <= Y < n and visited[Y][X] == 0:
                if arr[Y][X] == 0:
                    q.append((Y, X))
                    visited[Y][X] = visited[y][x] + 1
                else:
                    ans = visited[y][x] + 1
                    isShark = 1
        if isShark:
            break

    return ans


ans = 0
for y in range(n):
    for x in range(m):
        if arr[y][x] != 1:
            if ans < bfs(y, x):
                ans = bfs(y, x)

print(ans)

정답이지만 아무래도 상어가 있지 않은 모든 원소에 대하여 bfs()를 진행하다보니 시간이 매우 오래걸린다.

역발상을 해보자 (내가 한 것은 아니고 다른 분의 풀이이다)

상어의 위치를 기준으로 한칸씩 이동하면서 이동한 결과를 큐에 넣어가며 풀어보자는 것이다. 다시 말하면 상어들의 위치를 파악 후 큐에 넣은 다음, bfs를 통해 이동거리를 늘려가면 된다.

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
arr = []

shark = deque()
for i in range(n):
    temp = list(map(int, input().split()))
    for t in range(m):
        if temp[t] == 1:
            shark.append((i, t))
    arr.append(temp)

mx = [-1, -1, -1, 0, 1, 0, 1, 1]
my = [-1, 0, 1, 1, 1, -1, 0, -1]


def bfs():
    while shark:
        x, y = shark.popleft()
        for k in range(8):
            dx = x + mx[k]
            dy = y + my[k]
            if 0 <= dx < n and 0 <= dy < m:
                if arr[dx][dy] == 0:
                    shark.append((dx, dy))
                    arr[dx][dy] = arr[x][y] + 1
    return


bfs()
safe_dist = 0
for i in range(n):
    for j in range(m):
        safe_dist = max(safe_dist, arr[i][j])

print(safe_dist - 1)

이렇게 하면 원소별로 bfs() 를 모두 진행할 필요 없이 bfs() 한 번의 실행으로 매우 빠르게 연산이 가능하다.

시간 감소 !