[Silver II] 아기 상어 2 - 17086 (BFS)

[Silver II] 아기 상어 2 - 17086

문제 링크

성능 요약

메모리: 116364 KB, 시간: 212 ms

분류

너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

풀이방법

두 가지 풀이 방법을 공유한다. 두 번째 방법이 가장 쉽다.

첫 번째 방법 : 아기 상어(1)가 있는 곳을 하나씩 큐에 넣어 bfs함수를 돌려 거리를 +1씩 더해준다. graph의 값이 0이 아닌 거리가 기록된 값 중 더 작은 거리가 있다면 초기화해준다.

from collections import deque
n, m = map(int,input().split())
graph = []
for i in range(n):
  graph.append(list(map(int,input().split())))

dx = (0,0,1,-1,1,-1,1,-1)
dy = (1,-1,0,0,1,-1,-1,1)

for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      visited = [[False] * m for _ in range(n)]
      visited[i][j] = True
      q = deque()
      q.append((i,j))
      while q:
        x, y = q.popleft()
        
        for k in range(8):
          nx = dx[k] + x
          ny = dy[k] + y
          if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 1 and not visited[nx][ny]:
            if (graph[nx][ny] != 0 and graph[x][y] + 1 < graph[nx][ny]) or graph[nx][ny] == 0:
              visited[nx][ny] = True
              graph[nx][ny] = graph[x][y] + 1
              q.append((nx,ny))
print(max(map(max, graph))-1)

 

두 번째 방법 : 아기 상어(1)가 있는 모든 곳을 한 번에 큐에 다 담아 bfs함수를 실행하여 거리를 +1씩 기록해준다. 그 후 graph 리스트의 최댓값 -1 을 출력.

from collections import deque
n, m = map(int,input().split())
graph = []
for i in range(n):
  graph.append(list(map(int,input().split())))

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))
while q:
  x, y = q.popleft()

  for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
      graph[nx][ny] = graph[x][y] + 1
      q.append((nx,ny))
print(max(map(max, graph))-1)