[백준] 17086번: 아기 상어 2 - Python

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

 

아이디어

• 상어의 위치를 기준으로 bfs를 하자
• 1번상어와 2번상어의 거리와 2번 상어와 1번 상어의 거리는 같으니 반복해서 탐색 할 필요가 없음
  • li값이 0이 아닌 부분만 탐색
  • 한번 탐색한 li[y][x] 값을 이전 값의 +1 한 값을 넣어 거리와 탐색 했다 안했다를 동시에 지정
• bfs 탐색이 모두 끝난 후 li의 최대 값의 -1 한값 출력
  • 첫 시작을 1부터 했으니 -1을 해줘야 함

 

구현

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

N, M = map(int, input().split())

li = [list(map(int, input().strip().split())) for _ in range(N)]

mv =  [(-1,-1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]

# 1 상어 위치 탐색
pt = deque()
for i in range(N):
    for j in range(M):
        if li[i][j] == 1:
            pt.append((i, j))

# 2 상어 위치 기준으로 bfs 진행
# 거리는 이전 위치의 값에서 + 1한 값으로 계산
while pt:
    y, x = pt.popleft()
    for dy, dx in mv:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < N and 0 <= nx < M:
            if li[ny][nx] == 0:
                pt.append((ny, nx))
                li[ny][nx] = li[y][x] + 1


result = 0

# 최대 거리 탐색
for i in li:
    result = max(max(i), result)

# 1부터 시작했으니 -1
print(result-1)

 

 

마무리

오랜만에 bfs 문제다 대충 구조는 머리속에 남아있었지만 좀 버벅 거렸다.

dfs로 풀 수도 있을 거 같지만 최단거리를 구하는 문제는 bfs로 푸는게 최적이다.

기억해두자.

최단거리는 BFS