반응형
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크
www.acmicpc.net
bfs + heapq로 풀어낼 수 있는 문제.
현재 위치에서
1. bfs로 '잡아먹을 수 있는 물고기 좌표'를 탐색한다.
2. 탐색한 물고기 좌표를 heapq 자료구조에 저장한다. 자료구조의 정렬 우선순위는 '거리, y좌표, x좌표'다.
3. 잡아먹은 물고기 개수를 업데이트한다. 상어 크기와 같아질 경우 상어 크기를 1 키우고 잡아먹은 물고기 개수를 초기화한다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 2019 카카오 recruit - 무지의 먹방 라이브 (Level 3) (0) | 2020.03.25 |
|---|---|
| [Python] 프로그래머스. 2018 카카오 recruit - 캐시 (Level 2) (0) | 2020.03.24 |
| [Python] 구름. 공연 좌석 (0) | 2020.03.19 |
| [Python] 구름. 달걀 부화기 (0) | 2020.03.18 |
| [Python] 구름. 외주 (0) | 2020.03.17 |