[백준 17086] 아기 상어2 (with Python / BFS)

문제링크

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

17086번: 아기 상어 2

문제설명

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1 

2

 

문제풀이

처음시도한 방법 (이것도 정답코드)

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [0, 1, -1, 0, -1, 1, -1, 1]

def BFS(x, y):
    queue = deque([(x, y, 0)])
    visited[x][y] = 1

    while queue:
        curX, curY, dist = queue.popleft()

        if graph[curX][curY] == 1:
            return dist

        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                queue.append((nx, ny, dist+1))
                visited[nx][ny] = 1

tmpSet = set()

for i in range(N):
    for j in range(M):
        visited = [[0 for _ in range(M)] for _ in range(N)]
        if graph[i][j] == 0:
            tmpSet.add(BFS(i, j))

print(max(list(tmpSet)))

# 1. 각 좌표마다 1을 만날때까지 BFS 시행하여 최단거리 구해서 임시배열에 저장
# 2. 임시 배열에서 최댓값 구하기

하지만 난 모든 빈 좌표에서 BFS를 시행하여 상어까지의 최단거리를 구했다.

좀 더 최적화가 필요해보여서 생각해낸 방법이,

 

상어가 있는 좌표들에서 시작을 해보자 

=> 연산속도가 훨씬 빨라진다. (4000ms -> 72ms)

 

★핵심

1. 상어가 있는 좌표들을 큐에 전부 삽입.

2. 그러고 나서 큐에 있는거 기반으로 BFS 시행

3. BFS 직후 저장된 안전거리들의 최댓값 산출

코드

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, 1), (0, -1), 
     (-1, -1), (-1, 1), (1, -1), (1, 1)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
queue = deque()

def BFS():
    while queue:
        curX, curY = queue.popleft()

        for dx, dy in d:
            nx = curX + dx
            ny = curY + dy
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                if visited[nx][ny] == -1:
                    visited[nx][ny] = visited[curX][curY] + 1
                    queue.append((nx, ny))

# 상어좌표 전부 큐에 삽입
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))
            visited[i][j] = 0

# 큐에 좌표 삽입했으니, BFS 시행
BFS()

# BFS 종료후 visited에 삽입된 안전거리의 최댓값 구하기
maxValue = 0
for row in visited:
    maxValue = max(maxValue, max(row))

print(maxValue)

# 상어가 있는 1인 좌표에서 부터 BFS시행 (최단거리를 잼)