C++ - (백준) 16236번 아기상어
*문제
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가��
www.acmicpc.net
0. 전체 코드
github.com/ImYurim/Algorithm/blob/main/%EC%95%84%EA%B8%B0%EC%83%81%EC%96%B4.cpp
ImYurim/Algorithm
Contribute to ImYurim/Algorithm development by creating an account on GitHub.
github.com
1. idea
1) 아기상어 현재 위치에서 가장 가까운 물고기들중에 자기가 먹을 수 있는 물고기들을 어떻게 알게 할까?
-> 상어의 크기와 먹은 횟수를 세야한다. 상어크기가 변하면 먹은 횟수 초기화 해줘야한다.
-> 전체 칸에 있는 물고기들을 한번에 고려하는게 아니라 가까이 있는 상하좌우 애들부터 거리를 따져 나간다.
-> 그러려면 각 칸에 있는 물고기들에게 아기상어가 먹을 우선순위, 거리, 현재 상어의 크기 값을 부여해야한다. -> Min heap을 이용하고 우선순위는 거리>가장위>가장왼쪽 이다.
2) 갔던 길 체크는 언제마다 해줘야하는걸까?
-> 물고기를 하나 먹고나면 갔던 길 체크해줬던 걸 초기화해줘야한다.
* 정리
if 상 하 좌 우를 탐색해서 먹을 수 있는 물고기가 존재한다. -> 상어와 물고기 크기 비교
if 먹을 수 있는 물고기가 여러 마리인가
가장위 그다음 가장 왼쪽 이 순서로 먹는다.
else 존재안한다.
if 상 하 좌 우 에 지나갈 수 있는 곳이 있다
else 엄마한테 도움 요청 (끝)
2. 알아야 하는 것
- 우선순위큐로 최소 힙 구현
- 우선순위큐는 최대 힙이므로 연산자 오버로딩해줘야함
- 오버로딩 위해서는 operator를 알아야함
priority_queue 사용법
알고리즘문제를 풀며 원하는 기준에 따라 정렬한 후 하나씩 추출하고자할 때 priority_queue를 쓰면 어렵지않게 문제를 풀 수 있다. 가장 간단한 형태로써 priority_queue<자료형> pq; 라고 선언했을 때는
dolphins-it.tistory.com
C++ 연산자 오버로딩
안녕하세요 열코입니다. 저번시간에 함수 오버로딩에 대해 알아보았는데요. 이번시간에는 연산자 오버로딩에 대해 알아보도록 하겠습니다. ☞ 연산자 오버로딩이란 기존의 제공하고 있는 연��
yeolco.tistory.com
- memset( ) : 메모리 초기화 한꺼번에 하는 함수
twpower.github.io/79-usage-of-memset-function
[C, C++] memset 함수 사용하기
Practice makes perfect!
twpower.github.io
3. 구현 순서
- bfs 함수
1) 상어가 현재 있는 위치에 물고기를 먹을 수 있냐 없냐 판단한 후
2) 먹을 수 있는 경우 먼저 작성 -> 먹은 후 변화 코드 작성 해주고 -> 여태까지 갔던 위치 check해놓은것 초기화 해주고 -> 먹을 수 있는 물고기 찾기까지 큐에 다음 후보 애들 들어있는거 pop해서 없애줌 (그 전위치에서 먹을 후보들 큐에 넣어놓은거중에 먹을 수 있는 애 찾았으니 그 뒤에 후보애들은 볼필요 없다! 새로 큐 작성해야한다!)
3) 현재 위치에서 상하좌우로 갈 수 있는 곳 큐에 다 넣어준다.