[백준] #17086 아기 상어 2 파이썬

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

문제

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

---

복기

1. 상하좌우가 아니라 대각선도 포함인 독특한 문제였다.

2. 최대 안전거리여서 DFS로 풀어야 할줄 알았는데 최대최소는 BFS로 풀자.

3. (0, 0)에서 시작하지 말고 아기 상어의 위치에서부터 탐색을 하면 된다.

4. 너무 루틴하게 visited로 풀려고 하니까 다소 꼬였다. 더 문제를 이해하려고 노력하자.

5. x, y는 row와 column !!

 

---

솔루션

from collections import deque

N, M = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(N)]
distance  = [[-1 for _ in range(M)] for _ in range(N)]

dx = [0, 0, 1, -1, 1, 1,-1,-1]
dy = [1, -1, 0, 0, 1,-1, 1,-1]


q = deque()

for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            q.append((i, j))
            distance[i][j] =0

# bfs 수행
while q:
    x, y = q.popleft()
    for d in range(8):
        nx, ny = x + dx[d], y + dy[d]
        if 0<=nx<N and 0<=ny<M and distance[nx][ny] == -1:
            distance[nx][ny] = distance[x][y] + 1
            q.append((nx, ny))

max_distance = max(max(row) for row in distance)

print((max_distance))