[백준 17086번] 파이썬 - 아기 상어 2

백준 17086 - 아기 상어 2

시간 제한 2초, 메모리 제한 512MB

# 조건

• N×M 크기의 공간에 아기 상어 여러 마리가 있다.
• 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다.
• 한 칸에는 아기 상어가 최대 1마리 존재한다.
• 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다.
• 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
• 안전 거리가 가장 큰 칸을 구해보자.

입력

• 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다.
• 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다.
• 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

• 첫째 줄에 안전 거리의 최댓값을 출력한다.

# 접근 방법

• 입력받은 공간을 순회하며 상어의 위치를 q에 담아준다.
• delta함수를 문제에서 주어진 대로 8방향으로 기록해주고 bfs를 돌려준다.
• 이 때, 빈 칸에서 bfs함수를 시작하는 것이 아닌 상어의 위치에서 시작하여 돌려준다.
• visited를 순회하며 가장 큰 값을 출력하면 된다.

& 상어 기준 bfs

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    while q:  
        si, sj = q.popleft()  
        for d in range(8):  
            ni, nj = si + di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<M and not visited[ni][nj] and not arr[ni][nj]:  
                    q.append((ni, nj))  
                    visited[ni][nj] = visited[si][sj] + 1  

N, M = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
q = deque()  
visited = [[0] * M for _ in range(N)]  

for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 1:  
            q.append((i, j))  
            visited[i][j] = 1  

# 상하좌우 왼위 왼아 오위 오아  
di, dj = [-1, 1, 0, 0, -1, 1, -1, 1], [0, 0, -1, 1, -1, -1, 1, 1]  
bfs()  

result = 0  
for i in visited:  
    result = max(result, max(i) - 1)  
print(result)

& 빈 칸 기준 bfs

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

def bfs(ci, cj):
    global result
    q = deque()
    q.append((ci, cj))
    visited = [[0] * M for _ in range(N)]
    visited[ci][cj] = 1
    while q:
        si, sj = q.popleft()
        if (si, sj) in sharks:
            if visited[si][sj] -1 > result:
                result = visited[si][sj]-1
            return
        for d in range(8):
            ni, nj = si + di[d], sj + dj[d]
            if 0<=ni<N and 0<=nj<M and not visited[ni][nj]:
                q.append((ni, nj))
                visited[ni][nj] = visited[si][sj] + 1

N, M = map(int, input().split())
arr = [[*map(int, input().split())] for _ in range(N)]
sharks = set()
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            sharks.add((i, j))

# 상하좌우 왼위 왼아 오위 오아
di, dj = [-1, 1, 0, 0, -1, 1, -1, 1], [0, 0, -1, 1, -1, -1, 1, 1]
result = 0
for i in range(N):
    for j in range(M):
        bfs(i, j)
print(result)

• 똑같은 그래프 탐색이라도 어떤 방법으로 하는 것이 효율적일지 고민해보는 것은 위와 같은 시간 차이를 만들어낸다!!