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

문제

17086번: 아기 상어 2

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 상어의 위치를 확인하고 상어의 위치부터 bfs 탐색을 수행한다.

- bfs 탐색을 하면서 탐색하기까지 걸린 이동 횟수를 체크한다.

- 이동 횟수의 최댓값에서 처음 시작 값을 빼고 출력한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs():
    # 상/하/좌/우/대각선
    dx = [1, -1, 0, 0, 1, -1, 1, -1]
    dy = [0, 0, 1, -1, 1, -1, -1, 1]

    while queue:

        x, y = queue.popleft()

        # 상/하/좌/우/대각선 탐색
        for i in range(8):
            a = x + dx[i]
            b = y + dy[i]

            # 범위 내에 있고 탐색하지 않은 곳이라면 탐색
            if 0 <= a < n and 0 <= b < m:
                if visited[a][b] == 0:
                    # 탐색하기 까지 걸린 이동 횟수를 체크
                    visited[a][b] = visited[x][y] + 1
                    queue.append((a, b))


n, m = map(int, sys.stdin.readline().split())

# 상어가 있는 위치를 확인하고 그래프로 표현
visited = []
queue = deque()
for i in range(n):
    graph = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if graph[j] == 1:
            queue.append((i, j))
    visited.append(graph)

bfs()

# 이동 거리에 최대 값을 구하고 처음 시작값을 뺀다.
dist = 0
for i in range(n):
    for j in range(m):
        dist = max(dist, visited[i][j])

print(dist - 1)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법