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

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

bfs

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

---

현장에서 모의고사로 푼 풀이

from collections import deque
import sys
input = sys.stdin.readline

# 일단 델타 탐색 써야하는건 거의 무조건같음.
# 안전 거리의 최댓값을 어케구하지?
# 각 상어 기준으로 거리를 다 계산한담에 max때리면 되지 않을까?
# 각 상어 기준으로 거리를 다 구하고, 거기서 max를 구한 뒤에, 이걸 다시 max
# 그럼 거리는 델타 탐색에 bfs 엮어 쓰면 될거 같은데
# => 해보니 시간 초과남 아
# 산불 문제 이거 아니었는거같음 큐에 미리 다 넣고 시작했음
# 애초에 그럼 bfs를 여러번 돌릴 필요가 없음.

n, m = map(int, input().split())

# 상 하 좌 우 우상 우하 좌하 좌상 델타값 정의
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, 1, 1, -1, -1]

matrix = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
distances = [[-1] * m for _ in range(n)]

queue = deque()
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append((i, j, 0))
            visited[i][j] = True
            distances[i][j] = 0


max_distance = 0
while queue:
    # queue가 빌 때까지 실행
    x, y, dist = queue.popleft()
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False:
            visited[nx][ny] = True
            distances[nx][ny] = dist + 1
            # 걍 바로바로 최대 안전 거리 구해버리자
            max_distance = max(max_distance, dist + 1)
            queue.append((nx, ny, dist + 1))
#
# for shark in sharks:
#     visited = [[False] * m for _ in range(n)]
#     local_map = [[0] * m for _ in range(n)]
#     bfs(shark)
#     # print(*local_map, sep = '\n')
#     # print()
#     for i in range(n):
#         for j in range(m):
#             answer_map[i][j] = min(answer_map[i][j], local_map[i][j])

# print(*answer_map, sep = '\n')
#
# max_global_distance = 0
# for i in range(n):
#     for j in range(m):
#         max_global_distance = max(max_global_distance, answer_map[i][j])

print(max_distance)

산불조심, 토마토랑 거의 똑같은 문제!!

---

집와서 다시 풀어본 풀이