백준 17086
-
[백준] 17086번 아기 상어 2 (by Python)Programming/Algorithm 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 coll..