백준 17086 - 아기 상어 2 (파이썬)

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

풀이

1. 입력 처리

N, M = map(int, input().split())
A = [[] for _ in range(N)]

for i in range(N):
    A[i] = list(map(int, input().split()))

• N, M을 통해서 맵의 크기를 입력 받고,
• A배열에는 N * M 크기의 2차원 리스트를 생성하여, 각 좌표에 대한 정보를 저장하기 위해 사용

1. BFS 탐색을 위한 초기 설정

visit = [[False] * M for _ in range(N)]
dist = [[-1] * M for _ in range(N)]
queue = deque()

• visit : 방문 여부를 저장하는 2차원 리스트 (True : 방문함, False : 방문 안 함)
• dist : 해당 좌표에서 가장 가까운 상어까지의 거리를 저장하는 2차원 리스트 (1로 초기화)
• queue : BFS 탐색을 위한 큐 (BFS는 큐를 이용한 탐색 방식)

1. 상어의 위치를 큐에 추가

for i in range(N):
    for j in range(M):
        if A[i][j] == 1:
            queue.append((i, j))
            visit[i][j] = True
            dist[i][j] = 0

• 모든 상어(1)의 위치를 큐에 추가하고, 방문 처리 (visit[i][j] = True)
• 상어가 있는 곳의 거리(dist[i][j])는 0으로 설정

1. BFS를 이용한 거리 계산

dc = [-1, -1, -1, 0, 0, 1, 1, 1]
dr = [-1, 0, 1, -1, 1, -1, 0, 1]

8방향(상, 하, 좌, 우, 대각선)으로 이동할 수 있도록 dr, dc 배열을 설정.

while len(queue) != 0:
    r, c = queue.popleft()

    for i in range(8):
        nr, nc = r + dr[i], c + dc[i]
        if nr < 0 or N <= nr or nc < 0 or M <= nc:
            continue

        if not visit[nr][nc]:
            queue.append((nr, nc))
            visit[nr][nc] = True
            dist[nr][nc] = dist[r][c] + 1

• BFS를 이용해 상어가 없는 칸까지의 최단 거리를 계산.
• 현재 위치 (r, c)에서 8방향을 탐색하여 이동 가능하면 dist[nr][nc] = dist[r][c] + 1로 업데이트.
• 방문한 칸은 visit[nr][nc] = True로 표시하여 중복 탐색 방지.

시간 복잡도 분석

• BFS 탐색은 O(N*M), 즉, 맵의 크기에 비례하는 시간이 소요됨.
• N, M ≤ 50이므로 최악의 경우 50 * 50 = 2500개의 노드 탐색 → 충분히 빠름.

코드

# 백준 17086 - 아기 상어 2
# 분류 : 그래프, BFS

from collections import deque

N, M = map(int, input().split())
A = [[] for _ in range(N)]

for i in range(N) :
    A[i] = list(map(int, input().split()))

visit = [[False] * M for _ in range(N)]
dist = [[-1] * M for _ in range(N)]
queue = deque()

for i in range(N) :
    for j in range(M) :
        if A[i][j] == 1 :
            queue.append((i, j))
            visit[i][j] = True
            dist[i][j] = 0

dc = [-1, -1, -1, 0, 0, 1, 1, 1]
dr = [-1, 0, 1, -1, 1, -1, 0, 1]

while len(queue) != 0 :
    r, c = queue.popleft()

    for i in range(8) :
        nr, nc = r + dr[i], c + dc[i]
        if nr < 0 or N <= nr or nc < 0 or M <= nc :
            continue
        
        if not visit[nr][nc] :
            queue.append((nr, nc))
            visit[nr][nc] = True
            dist[nr][nc] = dist[r][c] + 1

print(max([max(dist[i]) for i in range(N)]))