[백준(BOJ)] 17086번 : 아기 상어 2 - PYTHON[파이썬]

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

17086번: 아기 상어 2

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

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

 

---

 

⊙ 문제 접근 과정

 

1의 좌표를 큐에 넣어준다.

그리고 8방향에 대해 bfs를 돌려준다. 이때 이동거리를 누적하여 더해준다.

 

마지막에 가장 큰 안전거리 값을 출력해주면 된다.

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

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

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


def bfs():
    while q:
        x, y = q.popleft()
        for k in range(8):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if arr[nx][ny] == 0:
                q.append([nx, ny])
                arr[nx][ny] = arr[x][y] + 1


bfs()
dist = 0
for i in range(N):
    for j in range(M):
        dist = max(arr[i][j], dist)

print(dist-1)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!