[백준] 17086번 아기 상어 2 (by Python)

 

문제

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

17086번: 아기 상어 2

 

풀이

    처음에는 각 칸에서 최소 거리를 구하는 아이디어를 떠올렸지만 computation cost가 너무 클 것 같다는 생각이 들었다. 그래서 빈칸에서 상어까지의 거리를 구할 것이 아니라 상어로부터 각 칸의 최소 거리를 propagate하는 방식으로 저장하면 보다 효율적일 것 같다고 생각했고, 다행히 시간 초과에 걸리지 않았다.

import sys
from collections import deque

input = sys.stdin.readline

INF = int(1e9)
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 0
steps = [(1, 0), (0, 1), (1, 1), (-1, -1), (-1, 0), (1, -1), (-1, 1), (0, -1)]
distance = [[INF] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q = deque()
            q.append((i, j, 1))
            distance[i][j] = 0
            while q:
                x, y, dist = q.popleft()
                for step in steps:
                    next_x, next_y = x + step[0], y + step[1]
                    if 0 <= next_x < n and 0 <= next_y < m and distance[next_x][next_y] > dist and arr[next_x][next_y] == 0:
                        distance[next_x][next_y] = dist
                        q.append((next_x, next_y, dist + 1))

print(max(max(d) for d in distance))

    위와 같이 상어를 찾고, 거리를 업데이트해나가는 방법으로 구현하였다.