[Python] 17086번 아기 상어 2

✏️ 문제

 

문제 파악

최댓값을 출력하므로 BFS를 활용하여 풀었다.

 

아기 상어의 위치에서 공간 내 거리가 각각 얼마나 걸리는 지 safety 배열에 담았다.

그리고 A 아기 상어에서 멀어도 B 아기 상어에서의 거리가 더 가까우면 그 거리를 대입해야 하므로 min을 사용하여 safety 배열에 담았다. 

 

safety 이차원 배열에서 max 값을 구해야 하므로 max(safety) 쓰면 값이 안나온다! 주의하자!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 브루트포스 알고리즘

 

 

코드

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

n, m = map(int, input().split())
graph = [[0] * (m) for _ in range(n)]
safety = [[0] * (m) for _ in range(n)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
shark = []

for i in range(n):
  line = list(map(int, input().split()))
  for j in range(m):
    graph[i][j] = line[j]

    if line[j] == 1:
      shark.append([i, j])

def bfs(x, y):
  q = deque([(x, y)])
  visited = [[0] * (m) for _ in range(n)] 
  visited[x][y] = 1
  safety[x][y] = 0
  
  while q:
    x, y = q.popleft() 

    for i in range(8):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < m and visited[dx][dy] == 0 and graph[dx][dy] == 0:
        if safety[dx][dy] != 0:
          safety[dx][dy] = min(safety[dx][dy], safety[x][y] + 1)
        else:
          safety[dx][dy] = safety[x][y] + 1
        visited[dx][dy] = 1
        q.append([dx, dy])

for i in range(len(shark)):
  x = shark[i][0]
  y = shark[i][1]
  bfs(x, y)

max = 0
for i in range(n):
  for j in range(m):
    if max < safety[i][j]:
      max = safety[i][j]

print(max)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS