Programming/Algorithm
[백준] 17086번 아기 상어 2 (by Python)
oranz.23
2021. 4. 11. 18:00
문제
https://www.acmicpc.net/problem/17086
17086번: 아기 상어 2
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.
www.acmicpc.net
풀이
처음에는 각 칸에서 최소 거리를 구하는 아이디어를 떠올렸지만 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))
위와 같이 상어를 찾고, 거리를 업데이트해나가는 방법으로 구현하였다.