백준 16236 아기상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

소스 코드 

http://colorscripter.com/s/kwHP02Y

 

오답노트

1. 상어가 움직인 자리를 0으로 바꿔줘야 하는데 남겨놨음

2. 문제를 잘못 이해 :

   사이즈업할 때마다 먹은 물고기 수를 초기화해줘야 함

   (총 개수로 따져서 틀렸음)

3. BFS에서 방문체크는 큐에 넣을 때 해 줘야 함

   => 큐에서 뺄 때 체크하니까 메모리초과

4. 최적화하려고 물고기를 찾은 최소시간 변수를 만들었는데

   얘 때문에 틀렸었음

 

 

풀이방식

bfs를 돌려서 잡은 물고기가 0이면 엄마호출

잡은 물고기가 1개일 때와 여러 개일 때를 나눠서 생각

 

bfs를 돌릴 때 물고기를 발견했다고 바로 먹는 게 아니라

후보로 생각하고 hunt에 넣어놨다가 bfs가 끝나고 따져서 그 중 조건에 맞는 것만 먹기

 

먹은 물고기 수 늘려주고, 그 수에 따라 사이즈 결정