[BOJ] 백준 16236. 아기 상어

▶문제설명

[BOJ] 백준 16236. 아기상어

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

▶Hint

---

BFS 알고리즘을 활용해서 먹을 수 있는 물고기를 먹으러 가는데 걸리는 시간을 구하고, 먹을 수 있는 물고기들을 vector에 담는다.

- 먹으러 가는데 걸리는 시간이 동일한 물고기가 둘 이상일 경우는?

BFS를 통해 먹을 수 있는 물고기를 vector에 담아서 r(행)을 기준으로 오름차순으로 정렬하고, r이 동일한 경우 c(열)를 기준으로 오름차순 정렬하여 인덱스 [0]에 있는 물고기를 먹으면 가장 상단이면서 왼쪽에 있는 물고기를 먹을 수 있게 된다. 

- 아기 상어의 데이터 관리는?

전역변수로 관리하면 편하다. 

int shark_r, shark_c, shark_size, eat_num;

shark_r : 아기 상어가 위치한 행

shark_c : 아기 상어가 위치한 열

shark_size : 아기 상어의 크기

eat_num : 현재까지 먹은 물고기의 수

물고기를 먹고 나면 eat_num을 증가시키고 

shark_r과 shark_c를 물고기의 좌표로 저장한다.

shark_size 와 eat_num이 동일한 경우

shark_size를 1 증가시키고 eat_num에 0을 저장한다.

▶Solution