문제 링크입니다: https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크
www.acmicpc.net
백준에서 불 시리즈 문제를 풀었다면 무난하게 풀 수 있는 문제였습니다.
백준 4179번 불(https://jaimemin.tistory.com/834)
문제의 조건을 잘 읽는 것이 중요한데 이 부분을 계속 놓쳐서 시간이 좀 걸렸던 문제였습니다.
알고리즘은 아래와 같습니다.
1. 현재 아기 상어의 위치를 start 변수에 저장하고 해당 위치를 0으로 초기화해줍니다.
2. 큐에 위치를 넣어주고 시뮬레이션을 시작합니다.
3. 시뮬레이션을 위해 두 개의 우선순위 큐가 필요한데 하나는 아기 상어가 지나가는 경로를 위해 다른 하나는 먹이의 후보를 위해 필요합니다.
4. 경로는 시간, y, x 순서로 작을수록 높은 우선순위가 부여되고 먹이는 y, x 순서로 작을수록 높은 우선순위가 부여됩니다.
5. 핵심은 같은 거리 내에 있는 모든 후보를 비교하기 위해 경로 우선순위 큐의 크기만큼 반복문을 돌려 먹이 후보를 파악하는 것이였습니다.
6. 먹이 후보가 나타난다면 아기 상어는 더 멀리 움직일 필요가 없으므로 반복문을 탈출하고 더 이상 먹이를 찾을 수 없을 때까지 2 ~ 5 과정을 반복합니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 15662번 톱니바퀴(2) (0) | 2019.04.27 |
|---|---|
| 백준 16235번 나무 재테크 (2) | 2019.04.14 |
| 백준 14911번 궁합 쌍 찾기 (0) | 2019.04.10 |
| 백준 14913번 등차수열에서 항 번호 찾기 (0) | 2019.04.10 |
| 백준 14914번 사과와 바나나 나누기 (0) | 2019.04.09 |