[백준] 17086 - 아기 상어 2 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

17086번: 아기 상어 2

 

해당 문제는 너비 우선 탐색(bfs)으로 해결하는 문제입니다.

칸 마다 가장 가까운 상어와의 거리를 안전거리라 하며, 이 문제의 목표는 안전거리의 최댓값을 구하는 것입니다.

 

문제를 해결하기 위한 접근 방법은 두 가지가 있습니다.

방법 1) 빈 칸 마다 너비 우선 탐색을 통해 안전거리를 계산한 후 안전거리의 최댓값을 구한다.

방법 2) 상어의 위치에서 너비 우선 탐색을 진행하여 모든 칸의 안전 거리를 계산한 후 안전거리의 최댓값을 구한다.

 

두 방법으로 모두 실행한 결과 방법 2가 방법1보다 메모리와 시간 측면에서 모두 더 효율적이라는 결과가 나왔습니다.

 

전체 코드

방법 1

제출 언어: PyPy3

시간: 640ms

 

import sys
from collections import deque

def bfs(sr, sc):
    global N, M, mat, dy, dx, answer

    visited = [[ False ] * M for _ in range(N)]
    visited[sr][sc] = True

    que = deque([(sr, sc, 0)])

    while que:
        cr, cc, cd = que.popleft()

        for i in range(8):
            nr, nc = cr + dy[i], cc + dx[i]

            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
                if mat[nr][nc] == 1:
                    answer = max(answer, cd+1)
                    return
                
                else:
                    visited[nr][nc] = True
                    que.append((nr, nc, cd+1))


if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().strip().split())

    mat = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
    
    dy, dx = (-1, -1, 0, 1, 1, 1, 0, -1), (0, 1, 1, 1, 0, -1, -1, -1)
    answer = float('-inf')

    for i in range(N):
        for j in range(M):
            if mat[i][j] == 0:
                bfs(i, j)

    print(answer)

 

방법 2

제출 언어: PyPy3

시간: 188ms

 

import sys
from collections import deque

def bfs():
    global N, M, mat, dist_mat, dy, dx, que
    
    while que:
        cr, cc, cd = que.popleft()

        for i in range(8):
            nr, nc = cr + dy[i], cc + dx[i]

            if 0 <= nr < N and 0 <= nc < M:
                if dist_mat[nr][nc] == -1:
                    dist_mat[nr][nc] = cd + 1
                    que.append((nr, nc, cd+1))


if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().strip().split())

    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
    dist_mat = [[ -1 ] * M for _ in range(N)]
    dy, dx = (-1, -1, 0, 1, 1, 1, 0, -1), (0, 1, 1, 1, 0, -1, -1, -1)
    
    que = deque([])

    for i in range(N):
        for j in range(M):
            if mat[i][j] == 1:
                dist_mat[i][j] = 0
                que.append((i, j, 0))
    
    bfs()
    
    answer = max([ max(row) for row in dist_mat ])
    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊