백준 17086 - 아기 상어 2 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/17086
풀이
- 입력 처리
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차원 리스트를 생성하여, 각 좌표에 대한 정보를 저장하기 위해 사용
- 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는 큐를 이용한 탐색 방식)
- 상어의 위치를 큐에 추가
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으로 설정
- 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)]))
'Programming > 백준' 카테고리의 다른 글
백준 1303 - 전쟁 - 전투 (파이썬) (0) | 2025.03.06 |
---|---|
백준 14719 - 빗물 (파이썬) (0) | 2025.03.05 |
백준 2293 - 동전 1 (파이썬) (0) | 2025.03.04 |
백준 1062 - 가르침 (파이썬) (0) | 2025.03.03 |
백준 6550 - 부분 문자열 (파이썬) (0) | 2025.03.02 |
댓글
이 글 공유하기
다른 글
-
백준 1303 - 전쟁 - 전투 (파이썬)
백준 1303 - 전쟁 - 전투 (파이썬)
2025.03.06 -
백준 14719 - 빗물 (파이썬)
백준 14719 - 빗물 (파이썬)
2025.03.05 -
백준 2293 - 동전 1 (파이썬)
백준 2293 - 동전 1 (파이썬)
2025.03.04 -
백준 1062 - 가르침 (파이썬)
백준 1062 - 가르침 (파이썬)
2025.03.03