[BOJ/백준] 17086 아기 상어 2

 

#  17086 아기 상어
import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]

def bfs(x,y):
    deque = collections.deque()
    deque.append((x,y,0))
    visited = [[True]*M for _ in range(N)]
    visited[x][y] = True
    while deque:
        x,y,cnt = deque.popleft()
        if arr[x][y]:
            return cnt
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx <N and 0<=ny <M:
                if visited[nx][ny]:
                    deque.append((nx,ny,cnt+1))
                    visited[nx][ny] = False


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


arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            temp = bfs(x,y)
            result = max(temp,result)

print(result)

처음에는 각 점에서 BFS를 해서 상어와의 위치값이 가장 먼 값을 구하는 방법을 했다.

 

import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
N,M = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
shark = collections.deque()
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            shark.append((i,j,arr[i][j]))

while shark:
    x,y,dis = shark.popleft()
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny<M:
            if not arr[nx][ny]:
                arr[nx][ny] = 1
                shark.append((nx,ny,dis+1))


print(dis-1)

 두번째 풀이는 그 반대로, 상어를 기준으로 bfs를 진행했다. 어차피 bfs는 거리순으로 진행되기 때문에, 가장 마지막에 나오는 dis가 최대 거리이므로, 마지막 dis에서 1을 빼줬다.