문제
N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.
어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
안전 거리가 가장 큰 칸을 구해보자.
입력
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.
출력
첫째 줄에 안전 거리의 최댓값을 출력한다.
예제 입력 1
5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
예제 출력 1
2
예제 입력 2
7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1
예제 출력 2
2
코드
from collections import deque
n,m=map(int,input().split())
graph=[]
for i in range(n):
tmp=list(map(int,input().split()))
graph.append(tmp)
visited=[[0]*m for _ in range(n)]
dx=[0,0,-1,1,1,1,-1,-1]
dy=[1,-1,0,0,1,-1,-1,1]
def bfs(i,j):
queue=deque()
queue.append([i,j,0])
while queue:
a,b,k=queue.popleft()
for z in range(8):
newA = a + dy[z]
newB = b + dx[z]
if 0 <= newA < n and 0 <= newB < m and graph[newA][newB] != 1:
if visited[newA][newB] == 0 or visited[newA][newB] > k + 1:
visited[newA][newB] = k + 1
queue.append([newA, newB, k + 1])
for i in range(n):
for j in range(m):
if graph[i][j]==1:
bfs(i,j)
print(max(map(max,visited)))-
너비위주탐색인 bfs를 사용
-
1인지점부터 하나씩 넘어가면서 깊이를 저장하여 안전거리 최대치를 구한다.
ex)
graph
010
000
000 일 경우
visited
101
111
222 이런식으로 하나씩 탐색해 나가는 것이다
1이 여러개일경우 여러번 구하게되는데 그럴경우 안전거리가 작은값으로 반영하게된다.
graph
0010
0000
1000
visited
2101
1111
0123
이와같다.
-
이중배열에 그냥 max 혹은 min을 박으면 하나의 원소가아닌 한 줄을 출력한다.
-
이를 위해 max(map(max(list)) 혹은 min(map(min(list))을 사용하면 최대값 최소값의 원소를 구할 수 있다.
