문제
아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
시간 제한 2초
메모리 제한 512MB
- 공간의 크기 N x N
- 물고기 M마리, 아기상어 1마리
- 물고기의 크기 1 ~ 6 , 아기 상어의 최초 크기 2
- 아기 상어의 이동 방법 : 1초에 상하좌우로 인접한 한 칸씩 이동
- 아기 상어의 이동 조건
- 아기 상어보다 큰 물고기 : 먹을 수 없으며, 지나갈 수 없다.
- 아기 상어와 크기가 같은 물고기 : 먹을 수 없으나, 지나갈 수 있다.
- 아기 상어보다 작은 물고기 : 먹을 수 있으며, 지나갈 수 있다.
- 먹을 수 있는 물고기들 중 거리가 가장 가까운 > 가장 위쪽 > 가장 왼쪽 기준으로 우선순위를 정한다.
- 아기 상어가 물고기를 먹는 시간은 없다고 가정한다.
풀이
왜 BFS야?
아기 상어가 가장 가까운 거리에 있는 물고기를 먹어야 하므로,
최단 경로 알고리즘이 필요하다.
최단 경로 알고리즘은 대표적으로 BFS, 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘 등이 있다.
위 알고리즘들의 시간 복잡도를 비교해보자.
- BFS : O(V + E)
- 다익스트라 알고리즘 : O(V log V) -> 간선의 가중치가 서로 다른 경우
- 벨만-포드 알고리즘 : O(VE) -> 간선의 가중치가 음수인 경우
- 플로이드-워셜 알고리즘 : O(V^3) -> 모든 노드들 사이의 최단 경로를 구하는 경우
아기 상어 문제처럼 간선의 가중치가 동일한 문제에는 BFS가 가장 효율적이다.
핵심 알고리즘
1. 아기 상어의 초기 위치를 찾는다.
2. 어떤 물고기들을 먹을 수 있는지 체크 -> BFS
3. 상어가 해당 물고기를 먹으러 이동
4. 2 ~ 3 반복 -> While문을 통해 BFS 반복 수행
옵션 1. 자신의 크기와 같은 수의 물고기를 먹을 때마다 아기 상어의 크기 증가
옵션 2. 엄마 상어에게 도움을 요청한 경우(= 더 이상 먹을 물고기가 없는 경우) 결과 출력 -> 종료 조건
이 문제에서의 핵심 구현 포인트를 살펴보자.
1. 아기 상어의 이동 조건
# board : NxN 크기의 공간
# eatable = [] #먹을 수 있는 물고기 리스트
# q : deque() # 지나갈 수 있는 칸 저장
# case 0: 이동한 칸이 빈칸
# case 1: 아기 상어와 크기가 같은 물고기
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
q.append((nx, ny, dist+1))
# case 2: 아기 상어보다 크기가 작은 물고기
elif board[nx][ny] != 0 and board[nx][ny] < shark_size:
heapq.heappush(eatable, (dist+1, nx, ny))
- 아기 상어의 이동 조건
- 아기 상어보다 큰 물고기 : 먹을 수 없으며, 지나갈 수 없다.
- 아기 상어와 크기가 같은 물고기 : 먹을 수 없으나, 지나갈 수 있다. -> case 1
- 아기 상어보다 작은 물고기 : 먹을 수 있으며, 지나갈 수 있다. -> case 2
아기 상어보다 크기가 작은 물고기를 발견하면, eatable 리스트에 넣어 준다.
먹을 수 있는 물고기가 여러 마리인 경우, 어떤 물고기를 최우선으로 먹을지 결정하기 위해 heap을 사용하였다.
- heap : O(log N)
- sort() : O(N log N)
2. 상어의 크기 관리
# 2. 어떤 물고기들을 먹을 수 있는지 check
while True:
fish_info = bfs(shark_r, shark_c, shark_size)
if fish_info:
shark_r, shark_c, time = fish_info #3. 상어가 물고기를 먹으러 이동
board[shark_r][shark_c] = 0
exp += 1
res += time
# 4. 자신의 크기와 같은 수의 물고기를 먹을 때마다 아기 상어의 크기 증가
if exp == shark_size:
shark_size += 1
exp = 0
# 5. 엄마 상어에게 도움을 요청한 경우 : 종료
else:
print(res)
break
이해를 돕기 위해 While문 내부 코드를 전부 가져왔다.
While문 내에서 bfs를 반복 수행하여 결과값을 fish_info에 저장한다.
만약 fish_info에 값이 존재하면, 상어가 물고기를 먹고 exp를 1 증가시킨다.
exp가 shark_size(상어의 크기)와 같아지는 경우, 상어의 크기를 1 증가시킨다.
코드
from collections import deque
import sys
import heapq
input = sys.stdin.readline
'''
풀이 방법 : BFS
시간 복잡도 : BFS * 최대 먹을 수 있는 물고기의 수 = O(n^2) * O(n^2) = O(n^4)
공간 복잡도 : O(n^2)
1. 아기 상어의 초기 위치를 찾는다.
2. 어떤 물고기들을 먹을 수 있는지 체크 -> BFS
3. 상어가 해당 물고기를 먹으러 이동
4. 2 ~ 3 반복 -> While문을 통해 BFS 반복 수행
옵션 1. 자신의 크기와 같은 수의 물고기를 먹을 때마다 아기 상어의 크기 증가
옵션 2. 엄마 상어에게 도움을 요청한 경우(= 더 이상 먹을 물고기가 없는 경우) 결과 출력 -> 종료 조건
'''
# BFS
def bfs(r, c, shark_size):
visited = [[0] * n for _ in range(n)]
q = deque()
q.append((r, c, 0))
eatable = [] #먹을 수 있는 물고기 리스트
if not visited[r][c]:
visited[r][c] = 1
while q:
x, y, dist = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n: #공간의 범위를 초과하지 않고
if not visited[nx][ny]: #방문하지 않은 칸에 대해
visited[nx][ny] = 1 #방문 처리
# case 0: 이동한 칸이 빈칸
# case 1: 아기 상어와 크기가 같은 물고기
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
q.append((nx, ny, dist+1))
# case 2: 아기 상어보다 크기가 작은 물고기
elif board[nx][ny] != 0 and board[nx][ny] < shark_size:
heapq.heappush(eatable, (dist+1, nx, ny))
#여러 물고기들 중 가장 최우선순위 물고기 정보를 반환
if eatable: #heapq를 이용하여 O(log(n))에 처리
return [eatable[0][1], eatable[0][2], eatable[0][0]]
else: # 먹을 수 있는 물고기가 없는 경우 : 종료
return
if __name__ == "__main__":
n = int(input().rstrip('\n'))
board = []
for _ in range(n):
board.append(list(map(int, input().rstrip('\n').split())))
shark_size = 2 # 상어의 크기
exp = 0 # 상어의 경험치 : shark_size와 같아지면 shark_size + 1
res = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
# 1. 아기 상어의 초기 위치를 찾는다.
for r in range(n):
for c in range(n):
if board[r][c] == 9:
board[r][c] = 0
shark_r, shark_c = r, c #상어의 현재 위치 정보 저장
break
# 2. 어떤 물고기들을 먹을 수 있는지 check
while True:
fish_info = bfs(shark_r, shark_c, shark_size)
if fish_info:
shark_r, shark_c, time = fish_info #3. 상어가 물고기를 먹으러 이동
board[shark_r][shark_c] = 0
exp += 1
res += time
# 4. 자신의 크기와 같은 수의 물고기를 먹을 때마다 아기 상어의 크기 증가
if exp == shark_size:
shark_size += 1
exp = 0
# 5. 엄마 상어에게 도움을 요청한 경우 : 종료
else:
print(res)
break
아기 상어 문제는 정말 여러 번 풀어본 것 같다,,
얼마 전까진 골드 IV 였는데 어느새 골드 III으로 바뀌어 있었다👀
내가 생각해도 다른 골드 IV랑 비교했을 때 조금 어렵다고 느꼈다
구현 문제 더 열심히 풀어야지!!
'PS > BOJ' 카테고리의 다른 글
[백준] 23288. 🎲주사위 굴리기 2 (파이썬) (0) | 2023.08.04 |
---|---|
[백준] 21609. 상어 중학교 (파이썬) (0) | 2022.03.20 |
[백준] 17142. 연구소 3 (파이썬) (1) | 2022.02.28 |
[백준] 14503. 로봇 청소기 (파이썬) (0) | 2022.02.19 |