C++ - (백준) 16236번 아기상어

*문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

0. 전체 코드

github.com/ImYurim/Algorithm/blob/main/%EC%95%84%EA%B8%B0%EC%83%81%EC%96%B4.cpp

ImYurim/Algorithm

 

1. idea

1) 아기상어 현재 위치에서 가장 가까운 물고기들중에 자기가 먹을 수 있는 물고기들을 어떻게 알게 할까?

 -> 상어의 크기와 먹은 횟수를 세야한다. 상어크기가 변하면 먹은 횟수 초기화 해줘야한다.

 -> 전체 칸에 있는 물고기들을 한번에 고려하는게 아니라 가까이 있는 상하좌우 애들부터 거리를 따져 나간다.

 -> 그러려면 각 칸에 있는 물고기들에게 아기상어가 먹을 우선순위, 거리, 현재 상어의 크기 값을 부여해야한다. -> Min heap을 이용하고 우선순위는 거리>가장위>가장왼쪽 이다.

 

2) 갔던 길 체크는 언제마다 해줘야하는걸까?

 -> 물고기를 하나 먹고나면 갔던 길 체크해줬던 걸 초기화해줘야한다. 

 

* 정리

if 상 하 좌 우를 탐색해서 먹을 수 있는 물고기가 존재한다. -> 상어와 물고기 크기 비교 

  if 먹을 수 있는 물고기가 여러 마리인가

     가장위 그다음 가장 왼쪽 이 순서로 먹는다.

   

else 존재안한다.

  if 상 하 좌 우 에 지나갈 수 있는 곳이 있다

  else 엄마한테 도움 요청 (끝)

 

 

2. 알아야 하는 것

- 우선순위큐로 최소 힙 구현

- 우선순위큐는 최대 힙이므로 연산자 오버로딩해줘야함 

- 오버로딩 위해서는 operator를 알아야함

dolphins-it.tistory.com/43

priority_queue 사용법

yeolco.tistory.com/119

C++ 연산자 오버로딩

- memset( ) : 메모리 초기화 한꺼번에 하는 함수

twpower.github.io/79-usage-of-memset-function

[C, C++] memset 함수 사용하기

 

3. 구현 순서

- bfs 함수 

1) 상어가 현재 있는 위치에 물고기를 먹을 수 있냐 없냐 판단한 후 

2) 먹을 수 있는 경우 먼저 작성 -> 먹은 후 변화 코드 작성 해주고 -> 여태까지 갔던 위치 check해놓은것 초기화 해주고 -> 먹을 수 있는 물고기 찾기까지 큐에 다음 후보 애들 들어있는거 pop해서 없애줌 (그 전위치에서 먹을 후보들 큐에 넣어놓은거중에 먹을 수 있는 애 찾았으니 그 뒤에 후보애들은 볼필요 없다! 새로 큐 작성해야한다!) 

3) 현재 위치에서 상하좌우로 갈 수 있는 곳 큐에 다 넣어준다.