백준(17086) - 아기상어2 Python

백준(17086) - 아기상어2

문제풀이: BFS 알고리즘, 파이썬

해결방법

상어의 에서부터 한칸씩 이동하면서 이동한 결과를 큐에 넣어가며 풀면된다.

• 전체 맵을 입력받을 때 상어의 위치는 큐에 삽입한다.
• 각 상어 위치부터 BFS 탐색을 하면서 이동가능한 칸이 0이면 이동거리를 해당 칸에 저장한다. (이동 전 값 + 1) arr[dx][dy] = arr[x][y] + 1
• 맵을 확인 후 저장된 최댓값을 찾고 1을 빼고 출력한다.(처음 시작값이 상어의 위치 값인 1이므로)

예시)

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

큐에서 popleft()를 해서 한 단계씩 진행하기 때문에 위와 같은 결과가 나온다.

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

n, m = map(int, input().split())
arr = []

shark = deque()
for i in range(n):
    temp = list(map(int, input().split()))
    for t in range(m):
        if temp[t] == 1:
            shark.append((i,t))
    arr.append(temp)

mx = [-1, -1, -1, 0, 1, 0, 1, 1]
my = [-1, 0, 1, 1, 1, -1, 0, -1]


def bfs():
    while shark:
        x, y = shark.popleft()
        for k in range(8):
            dx = x + mx[k]
            dy = y + my[k]
            if 0 <= dx < n and 0 <= dy < m:
                if arr[dx][dy] == 0:
                    shark.append((dx,dy))
                    arr[dx][dy] = arr[x][y] + 1
    return


bfs()
safe_dist = 0
for i in range(n):
    for j in range(m):
        safe_dist = max(safe_dist, arr[i][j])

print(safe_dist - 1)

눈물이 앞을 가리는 실패의 흔적…