백준 문제풀이
17086번: 아기 상어 / silver 2 / BFS
RonLee
2023. 4. 7. 13:42
https://www.acmicpc.net/problem/17086
17086번: 아기 상어 2
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만
www.acmicpc.net
'''
17086번: 아기 상어 / silver 2 / BFS
'''
import sys
from collections import deque
input = sys.stdin.readline
# 1. n, m, graph 입력 받기 / 상어 위치 find 리스트에 담기
n, m = map(int, input().split())
find = deque()
graph = []
for x in range(n):
graph.append(list(map(int, input().split())))
for y in range(m):
if graph[x][y] == 1:
find.append((x, y))
# 2. graph 색칠하기 (BFS)
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
while find:
x, y = find.popleft()
now_value = graph[x][y]
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] == 0:
graph[nx][ny] = now_value + 1
find.append((nx, ny))
# 3. graph 에서 가장 큰 숫자 찾고, -1 해서 출력하기
max_res = 0
for lst in graph:
if max_res < max(lst):
max_res = max(lst)
print(max_res - 1)대략적인 로직은 주석 처리!
코드 리뷰
- 문제 이해 : 아기 상어가 위치해 있을 곳은, 상어와 거리가 멀리 떨어진 곳이어야 합니다.
- 해결 방법 :
<BFS>
상어들의 주변이 0일때, 2로 만듭니다. ->
2로 만든 위치의 주변이 0일때, 3으로 만듭니다. ->
3으로 만든 위치의 주변이 0일때, 4로 만듭니다. -> ...(반복)...
<출력>
graph에 가장 큰 값을 찾고, 큰 값의 -1 해서 출력합니다.
코드 리뷰를 하다보니 가장 큰 값을 찾는 #3 주석 부분을
BFS 알고리즘 실행 도중에 찾으면 더 효율적이라고 생각이 들었습니다. (쉬우니까 패쓰!0)