[Python] 백준/BOJ 17086번: 아기 상어 2 (Silver 2)

💻 Problem

문제 보러 가기

 

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

 

💡 Approach

상어의 위치를 기준으로 bfs를 퍼뜨려서 모든 칸의 안전 거리를 구하고 해당 배열의 칸들을 검사해서 안전 거리가 가장 큰 칸을 찾아 출력하도록 했다.

 

먼저 상어들의 위치를 찾아서 sharks 배열에 위치를 기억하고 보드의 상어 칸을 -1로 초기화한다.

빈 칸은 모두 INF 값으로 초기화한다.

• N * M

상어에서 다른 칸까지의 거리를 구한다.

각 상어의 위치를 시작점으로 하여 bfs를 돌린다.

• 상어의 수 * 9 * N * M

안전 거리의 최댓값을 구한다.

• N * M

시간을 모두 더하면 2NM + 상어의 수 * 9NM이다.

N과 M의 최댓값은 각각 50이다.

 

대입하면 2 * 50 * 50 + 상어의 수 * (9 * 50 * 50)

5 * 10^3 + 상어의 수 * 2 * 10^4

 

한 칸 빼고 모든 칸이 상어면 상어의 수 최댓값이 NM - 1인데

대입하면 4 * 10^3 + 2 * 10^4가 되므로 시간은 여유롭다. (시간제한 2초)

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

def bfs(shark):
    visited = [[False] * M for _ in range(N)]
    queue = deque([shark + (1,)])

    while queue:
        y, x, d = queue.popleft()
        
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx]:
                board[ny][nx] = min(board[ny][nx], d)
                queue.append((ny, nx, d + 1))
                visited[ny][nx] = True            

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
sharks = []
ans = 0

dy = [-1, 1, 0, 0, -1, -1, 1, 1]
dx = [0, 0, -1, 1, -1, 1, -1, 1]

# 상어의 위치 찾기
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            sharks.append((i, j))
            board[i][j] = -1
        else:
            board[i][j] = sys.maxsize

# 상어에서 다른 칸까지의 거리 구하기
for shark in sharks:
    bfs(shark)

# 안전 거리 최댓값 구하기
for i in range(N):
    ans = max(ans, max(board[i]))
print(ans)

하지만 지금 코드는 안전 거리를 보드에 기록하면서 상어와 빈칸(현재 탐색 중인 칸)과의 거리를 큐에 같이 넣고 있기 때문에 불필요한 계산이 반복된다.

bfs는 한 번만 돌려도 최단 거리로 갱신 가능한데 위 코드의 경우 상어의 수만큼 탐색을 하기 때문에 비효율적이다.

 

✏️ Solution

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

def bfs(sharks):
    queue = deque(sharks)
    max_dis = 0 # 안전 거리의 최댓값

    while queue:
        y, x = queue.popleft()
        
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < N and 0 <= nx < M:
                # 이전에 구한 안전 거리보다 새로 구한 안전 거리가 더 짧다면 갱신하기
                if visited[y][x] + 1 < visited[ny][nx]:
                    visited[ny][nx] = visited[y][x] + 1
                    max_dis = max(max_dis, visited[ny][nx])
                    queue.append((ny, nx))
    
    return max_dis

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[INF] * M for _ in range(N)]
sharks = []
ans = 0

dy = [-1, 1, 0, 0, -1, -1, 1, 1]
dx = [0, 0, -1, 1, -1, 1, -1, 1]

# 상어의 위치 찾기
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            sharks.append((i, j))
            visited[i][j] = 0

# 안전 거리 구하기
print(bfs(sharks))

거리를 큐에 기록하지 않고 visited에 기록하는 방법으로 바꿨다.

먼저 보드에 존재하는 상어들의 위치를 큐에 넣어놓고 탐색을 시작했다.

이전에 구한 안전 거리보다 새로 구한 안전 거리가 더 짧다면 갱신하여 안전 거리의 최단 거리를 보장했다.