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

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

17086번: 아기 상어 2

 

Difficulty : Silver 2

 

Status : Solved

 

Time : 00:04:20

 

---

 

문제 설명

 

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

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

 

출력 예시

 

2

 

 

---

 

풀이

 

모든 칸에 대해 각 아기상어와의 거리를 구하는 것은 매우 비효율 적이다. 잘 생각해보면, 아기 상어들을 시작점인 관점으로 다시 생각해 볼 수 있다. 그렇게 되면 각 칸은 아기상어 노드들에서 시작된 BFS경로중 최단값으로 변환되기 때문이다.

 

즉 한 번의 순회로 아기 상어들을 큐에 넣고, 그 큐를 토대로 BFS를 수행하면 모든 지점에서의 안전 거리를 구할 수 있다. 이 모든 지점의 최댓값을 구해주면 완료.

 

풀이 코드

from collections import deque
import sys
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
MAX = float('inf')

input = sys.stdin.readline
N, M = map(int, input().split())
map_list = [list(map(int, input().split())) for _ in range(N)]
q = deque()

visited = [[MAX]*M for _ in range(N)]
for i in range(N) :
  for j in range(M) :
    if map_list[i][j] == 1 :
      q.append((j, i, 0))
      visited[i][j] = 0

while q :
  x, y, dist = q.popleft()
  for k in range(8) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < M and -1 < ay < N and visited[ay][ax] > dist + 1:
      visited[ay][ax] = dist + 1
      q.append((ax, ay, dist + 1))

print(max(map(max, visited)))

풀이 완료!