[Baekjoon] BFS - 17086 아기상어 2 (오답노트)

문제

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

 

풀이

1. 상어 주변은 미리 제외해야 함.

   : 재탐색을 진행하면 안되기 때문에 미리 주변을 제외해야한다.

   (핵심: 주변을 미리 제외하려면 Queue에 미리 넣어서 BFS 탐색을 진행)

2. 상어로부터 먼 거리 확인

 

예시

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

 

# 미리 제외
0 2 1 2
2 2 2 2
1 2 0 0
2 2 2 2
0 0 2 1

# 이후 채워지지 않은 거리 채우기
3 2 1 2
2 2 2 2
1 2 3 3
2 2 2 2
3 3 2 1

 

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())
sharks = deque([])
maps = []
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for x in range(n):
    lines = list(map(int, sys.stdin.readline().rstrip().split()))
    for y, value in enumerate(lines):
        if value == 1:
            sharks.append((x, y))
    maps.append(lines)


def bfs():
    while sharks:
        cx, cy = sharks.popleft()
        
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if not (0 <= nx < n and 0 <= ny < m):
                continue

            if maps[nx][ny] == 0:
                maps[nx][ny] = maps[cx][cy] + 1
                sharks.append((nx, ny))


bfs()
max_value = 0

for x in range(n):
    for y in range(m):
        max_value = max(max_value, maps[x][y])

print(max_value - 1)